Re: Better algorithm than brute-force stack for combinatorial problems?

[kvale]

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.