查找总和为某个所需数字的数字组合 [英] Find combinations of numbers that sum to some desired number

问题描述

我需要一种算法，该算法可以识别一组总和为其他数字的数字的所有可能组合.

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

例如，给定集合{2,3,4,7}，我需要知道所有总计为x的可能子集.如果为x == 12，则答案为{2,3,7}；否则为{2,3,7}.如果x ==7，答案为{{3,4},{7}}(即两个可能的答案)；如果x==8，则没有答案.请注意，正如这些示例所暗示的那样，集合中的数字不能重复使用.

For example, given the set {2,3,4,7}, I need to know all possible subsets that sum to x. If x == 12, the answer is {2,3,7}; if x ==7 the answer is {{3,4},{7}} (ie, two possible answers); and if x==8 there is no answer. Note that, as these example imply, numbers in the set cannot be reused.

此问题

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

我知道这个问题很难解决(请参阅其他文章以进行讨论)，但是我只需要一个蛮力解决方案，因为我要处理的集合很小.

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

推荐答案

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's no point in trying a
      # non-final element unless it's 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;

这开始是

This started as a fairly direct translation of the C# version from the question you linked, but I simplified it a bit (and now a bit more, and also removed some unnecessary variable allocations, added some optimizations based on the list of elements being sorted, and rearranged the conditions to be slightly more efficient).

我现在还添加了另一个重要的优化.在考虑是否尝试使用无法完成总和的元素时，如果该元素大于或等于当前目标的一半是没有意义的. (我们添加的下一个数字会更大.)根据您尝试的设置，这可能会使短路更多. (您也可以尝试添加下一个元素，而不是乘以2，但是您必须担心会耗尽列表的末尾.)

I've also now added another significant optimization. When considering whether to try using an element that doesn't complete the sum, there's no point if the element is greater than or equal to half the current goal. (The next number we add will be even bigger.) Depending on the set you're trying, this can short-circuit quite a bit more. (You could also try adding the next element instead of multiplying by 2, but then you have to worry about running off the end of the list.)

这篇关于查找总和为某个所需数字的数字组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！