#! perl -slw
use strict;
use Memoize;
use Benchmark::Timer;
use List::Util qw[ sum ];

$|=1;
BEGIN{ @ARGV = map{ eval } @ARGV }

sub sums{
	INIT{ memoize( 'sums' ); }
	my $total = shift;
	return unless @_ or $total > 1;
	return $_[ 0 ] == $total ? $_[ 0 ]: () if @_ == 1;
	my @list;
	for my $i ( 0 .. $#_ ) {
		my $next = $_[ $i ];
		my $newTotal = $total - $next;
		for my $partial ( 
                sums( $newTotal, 
                      grep $_ <= $newTotal, @_[ grep $_ != $i, 0 .. $#_ ] 
                ) 
        ) {
			next unless $partial 
                  and sum( split ' ', $partial ) == $newTotal;
			push @list, "$next $partial"; 
		}
	}
	return @list;
}

my( $total, @list ) = ( shift @ARGV, @ARGV );

my $T = new Benchmark::Timer;

$T->start( 'memoized' );
my @sums3 = sums( $total, sort{ $b <=> $a } @ARGV );
$T->stop( 'memoized' );
$T->report;
<STDIN>;

__END__
P:\test>355455-3 30 1..20
1 trial of memoized (675.107ms total)

P:\test>355455-3 40 1..20
1 trial of memoized (11.674s total)