Summing Subsets

So, the third challenge was to count the number of subsets of a set of numbers such that the largest number in the subset is the sum of the rest of the numbers in the subset. My first attempt was very straightforward: create all the subsets and check to see if they have the desired property:

my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92,
 95, 97, 99;

my $hits = 0;

for 1..(2 ** +@a) -> $key {
    my @b = gather for 0..+@a -> $i { take @a[$i] if $key +& (2 ** $i); }
    my $test = @b.pop;
    next if $test != [+] @b;
    $hits++;
    say (@b, $test).join(' ');
}

say "$hits hits";

I think this works correctly, but it will be a long time before we know — as I type this, it’s been running for ten hours on my fastest computer, and I don’t anticipate it finishing any time soon.

My second attempt relies on recursion, the fact the list is sorted, and skipping fruitless branches to get the job done much faster — 47 seconds, to be precise.

sub CountSumSets($target, @a) {
    my $sets = 0;
    for ^ +@a -> $i {
        if @a[$i] < $target {
            $sets += CountSumSets($target - @a[$i], @a[($i + 1) .. (@a - 1)]);
        } elsif @a[$i] == $target {
            $sets += 1;
        }
    }
    $sets;
}


my @a = 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99;
@a .= reverse;

my $hits = 0;

for ^ +@a -> $i {
    $hits += CountSumSets(@a[$i], @a[($i + 1) .. (@a - 1)]);
}

say $hits;