#! 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)
[download]