你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?

一个简单的例子:

要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345


当前回答

另一个python解决方案是使用itertools.combination模块,如下所示:

#!/usr/local/bin/python

from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target
            ]   
        )   

    print results

if __name__ == "__main__":
    find_sum_in_list([3,9,8,4,5,7,10], 15)

输出:[(8,7),(5,10),(3,8,4),(3,5,7)]

其他回答

我在做类似的scala作业。我想在这里发布我的解决方案:

 def countChange(money: Int, coins: List[Int]): Int = {
      def getCount(money: Int, remainingCoins: List[Int]): Int = {
        if(money == 0 ) 1
        else if(money < 0 || remainingCoins.isEmpty) 0
        else
          getCount(money, remainingCoins.tail) +
            getCount(money - remainingCoins.head, remainingCoins)
      }
      if(money == 0 || coins.isEmpty) 0
      else getCount(money, coins)
    }

在Haskell:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

J:

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

正如您可能注意到的,两者都采用相同的方法,并将问题分为两部分:生成幂集的每个成员,并检查每个成员与目标的和。

还有其他的解决方案,但这是最直接的。

在这两种方法中,你是否需要帮助,或者找到另一种方法?

这是R中的一个解

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}

这个问题的一个迭代c++堆栈解决方案。与其他迭代解决方案不同的是,它不会对中间序列进行不必要的复制。

#include <vector>
#include <iostream>

// Given a positive integer, return all possible combinations of
// positive integers that sum up to it.

std::vector<std::vector<int>> print_all_sum(int target){
    std::vector<std::vector<int>> output;
    std::vector<int> stack;

    int curr_min = 1;
    int sum = 0;
    while (curr_min < target) {
        sum += curr_min;
        if (sum >= target) {
            if (sum == target) {
                output.push_back(stack); // make a copy
                output.back().push_back(curr_min);
            }
            sum -= curr_min + stack.back();
            curr_min = stack.back() + 1;
            stack.pop_back();
        } else {
            stack.push_back(curr_min);
        }
    }

    return output;
}

int main()
{
    auto vvi = print_all_sum(6);

    for (auto const& v: vvi) {
        for(auto const& i: v) {
        std::cout << i;
        }
        std::cout << "\n";
    }

    return 0;
}

输出print_all_sum (6):

111111
11112
1113
1122
114
123
15
222
24
33
func sum(array : [Int]) -> Int{
    var sum = 0
    array.forEach { (item) in
        sum = item + sum
    }
    return sum
}
func susetNumbers(array :[Int], target : Int, subsetArray: [Int],result : inout [[Int]]) -> [[Int]]{
    let s = sum(array: subsetArray)
    if(s == target){
        print("sum\(subsetArray) = \(target)")
        result.append(subsetArray)
    }
    for i in 0..<array.count{
        let n = array[i]
        let remaning = Array(array[(i+1)..<array.count])
        susetNumbers(array: remaning, target: target, subsetArray: subsetArray + [n], result: &result)
        
    }
    return result
}

 var resultArray = [[Int]]()
    let newA = susetNumbers(array: [1,2,3,4,5], target: 5, subsetArray: [],result:&resultArray)
    print(resultArray)