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