#!/usr/bin/perl -w
use strict;

sub partition
{
	my ($array_tree, $residual, $max) = @_;
	for my $i (reverse(1 .. $max)) {
		next if $residual < $i;
		my $branch = [$i];
		&partition($branch, $residual - $i, $i) if $residual > $i;
		push @$array_tree, $branch;
	}
}

sub traverse # and generate $array_output
{
	my ($array_tree, $array_output) = @_;
	LOOP: foreach my $branch (@$array_tree) {
		my @copy_output = @$array_output;
		push @copy_output, shift @$branch;
		if (@$branch > 0) {
			&traverse($branch, \@copy_output);
			next LOOP;
		}
		print join(' + ', @copy_output)."\n";
	}
}

my $n = shift @ARGV;
die "USAGE: $0 integer\n" if not defined $n;
my ($array_tree, $array_output) = ([], []);
&partition($array_tree, $n, $n);
&traverse($array_tree, $array_output);

__END__
* examples and data structure 

1 -> [[1]]
2 -> [[1, [1]]]
3 -> [[2, [1]], [1, [1, [1]]]]
4 -> ...
