in reply to Better algorithm than brute-force stack for combinatorial problems?

The problem you are solving is a variation of the Subset Sum problem, and is known to be NP complete. There exist algorithms that are a little better than brute force, but still exponential in the number of elements.

Here is my take on the problem:

my @check = qw/ 1 2 3 4 5 6 7 8 9 /; my $desired = 20; foreach my $index (0..2**@check-1) { my $sum = 0; foreach my $pos (0..@check-1) { my $bit = ($index >> $pos) % 2; $sum += $bit * $check[$pos]; } if ($sum == $desired) { my @combo; foreach my $pos (0..@check-1) { push @combo, $check[$pos] if ($index >> $pos) % 2; } print join " ", @combo, "\n"; } }
On a 32 bit machine, this works for up to 32 numbers.

-Mark

  • Comment on Re: Better algorithm than brute-force stack for combinatorial problems?
  • Download Code