Ehm... If you accept 3 in list of answers for input "3", then there should be 4 in list for "4", then total count for the latter would be 8, not 7. In fact, said count is equal 2**(N-1), rather than Tribonacci sequence with whatever initial triplet as your code implies.

Visualize it this way: there are N ones 1,1,1,.... You insert any number of pluses in between and perform these additions to get partial answer. So, emit all subsets of all positions, it should be clear enough. I'd NOT recommend to submit code below if this is HW assignment. Result is correct, algo is kind of joke.

use strict;
use warnings;
use Algorithm::Combinatorics 'subsets';

$" = ' + ';
use constant N => 5;
my $i = subsets [ 1 .. N - 1 ];

while () {
    my $s = '1,' x N;
    substr $s, 2 * $_ - 1, 1, '+'  
        for @{ $i-> next or last };
    print eval( $s = "@{[ eval $s ]}" ), 
        " = $s\n";
}

__END__

5 = 5
5 = 1 + 4
5 = 2 + 3
5 = 1 + 1 + 3
5 = 3 + 2
5 = 1 + 2 + 2
5 = 2 + 1 + 2
5 = 1 + 1 + 1 + 2
5 = 4 + 1
5 = 1 + 3 + 1
5 = 2 + 2 + 1
5 = 1 + 1 + 2 + 1
5 = 3 + 1 + 1
5 = 1 + 2 + 1 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

[download]

In reply to Re: problem while solving basic dynamic programming question by vr
in thread problem while solving basic dynamic programming question by yujong_lee

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.