Find combinations of numbers that add up to some desired number

Question

I need an algorithm that identifies all possible combinations of a set of numbers that add up to some other number.

For example, given the set {2,3,4,7}, I need to know all the possible subsets that add up with x. If x == 12, the answer will be {2,3,7}; if the x ==7answer {{3,4},{7}}(i.e. two possible answers); and if x==8there is no answer. Note that, as follows from this example, the numbers in the set cannot be reused.

This question was asked on this site a couple of years ago , but the answer is in C #, and I need to do it in Perl and not enough to know to translate the answer.

I know this problem is complex (see another post for discussion), but I just need a brute force solution because I am dealing with fairly small sets.

Answer 1

sub Solve
{
  my ($goal, $elements) = @_;

  # For extra speed, you can remove this next line
  # if @$elements is guaranteed to be already sorted:
  $elements = [ sort { $a <=> $b } @$elements ];

  my (@results, $RecursiveSolve, $nextValue);

  $RecursiveSolve = sub {
    my ($currentGoal, $included, $index) = @_;

    for ( ; $index < @$elements; ++$index) {
      $nextValue = $elements->[$index];
      # Since elements are sorted, there no point in trying a
      # non-final element unless it less than goal/2:
      if ($currentGoal > 2 * $nextValue) {
        $RecursiveSolve->($currentGoal - $nextValue,
                          [ @$included, $nextValue ],
                          $index + 1);
      } else {
        push @results, [ @$included, $nextValue ]
            if $currentGoal == $nextValue;
        return if $nextValue >= $currentGoal;
      }
    } # end for
  }; # end $RecursiveSolve

  $RecursiveSolve->($goal, [], 0);
  undef $RecursiveSolve; # Avoid memory leak from circular reference
  return @results;
} # end Solve


my @results = Solve(7, [2,3,4,7]);
print "@$_\n" for @results;

It started as a fairly direct translation of the C # version from a question related to you , but I simplified it a bit (and now a bit more, and also removed some unnecessary variable distributions, added some optimizations based on the list of sorted elements and rebuilt the conditions to be a little more effective).

. , , , , . ( , , .) , , . ( 2, , .)

Answer 2

Data::PowerSet, :

Answer 3

Algorithm::Combinatorics. , , . , .

#!/usr/bin/perl

use strict; use warnings;
use List::Util qw( sum );
use Algorithm::Combinatorics qw( combinations );

my @x = (1 .. 10);
my $target_sum = 12;

{
    use integer;
    for my $n ( 1 .. @x ) {
        my $iter = combinations(\@x, $n);
        while ( my $set = $iter->next ) {
            print "@$set\n" if $target_sum == sum @$set;
        }
    }
}

: , 40 . , .

Answer 4

:

"", , .

• , .
• , ,
• , / , , .
• else (, , , )
• .

, , , , . , , , k , k + 1 .

, . perl, , .

, , .

Answer 5

" "?

N! (.. (N-0) * (N-1) * (N-2)...), . : . , , . , .

, , . S1, T, T1, , T S1, , , S1 T1. N! .

, .

.

Answer 6

Someone posted a similar question some time ago, and another person showed a neat trick with a shell to answer it. Here is a shell technique, but I don’t think that it is as accurate a solution as what I saw before (therefore, I do not take responsibility for this approach). This is nice because it uses a shell extension:

for i in 0{,+2}{,+3}{,+4}{,+7}; do
  y=$(( $i )); # evaluate expression
  if [ $y -eq 7 ]; then
    echo $i = $y;
  fi;
done

Outputs:

0+7 = 7
0+3+4 = 7