#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(timethese);
sub solve1 {
my ( $goal, $elements ) = @_;
my ( @results, $RecursiveSolve, $nextValue );
$RecursiveSolve = sub {
my ( $currentGoal, $included, $index ) = @_;
for ( ; $index < @$elements ; ++$index ) {
$nextValue = $elements->[$index];
if ( $currentGoal > 2 * $nextValue ) {
$RecursiveSolve->(
$currentGoal - $nextValue,
[ @$included, $nextValue ],
$index + 1
);
}
else {
if ( $currentGoal == $nextValue ) {
push @results, [ @$included, $nextValue ];
}
return if $nextValue >= $currentGoal;
}
}
};
$RecursiveSolve->( $goal, [], 0 );
undef $RecursiveSolve;#Avoid memory leak from circular reference
return @results;
}
sub solve2 {
my $want = shift() or return [];
$want > 0 or return ();
my ( $first, @rest ) = @{ shift() } or return ();
map( [ $first, @$_ ], solve2( $want - $first, \@rest ) ),
solve2( $want, \@rest );
}
my @results;
my @tosolve=(869,[15,43,51,56,60,67,122,152,193,204,229,271,293,301]);
timethese(
1000,
{
'orig' => sub { solve1(@tosolve) },
'tybalt89' => sub { solve2(@tosolve) }
}
);