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
`

Comment onRe: problem while solving basic dynamic programming questionDownloadCode