find所有可能的数字组合，以达到给定的总和

你将如何去testing给定数字集合中的所有可能的组合增加到一个给定的最终数字？

例：

要添加的一组数字：{1,5,22,15,0，…}
预期结果：12345

这个问题可以通过recursion组合所有可能的总和来解决。这里是Python中的algorithm：

def subset_sum(numbers, target, partial=[]): s = sum(partial) # check if the partial sum is equals to target if s == target: print "sum(%s)=%s" % (partial, target) if s >= target: return # if we reach the number why bother to continue for i in range(len(numbers)): n = numbers[i] remaining = numbers[i+1:] subset_sum(remaining, target, partial + [n]) if __name__ == "__main__": subset_sum([3,9,8,4,5,7,10],15) #Outputs: #sum([3, 8, 4])=15 #sum([3, 5, 7])=15 #sum([8, 7])=15 #sum([5, 10])=15

下面的斯坦福大学的抽象编程讲座很好地解释了这种types的algorithm – 这个video非常值得推荐，以了解recursion如何生成解决scheme的排列。

编辑

以上作为生成器函数，使其更有用。需要Python 3.3+，因为yield from 。

 def subset_sum(numbers, target, partial=[], partial_sum=0): if partial_sum == target: yield partial if partial_sum >= target: return for i, n in enumerate(numbers): remaining = numbers[i + 1:] yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

以下是相同algorithm的Java版本：

 package tmp; import java.util.ArrayList; import java.util.Arrays; class SumSet { static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) { int s = 0; for (int x: partial) s += x; if (s == target) System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target); if (s >= target) return; for(int i=0;i<numbers.size();i++) { ArrayList<Integer> remaining = new ArrayList<Integer>(); int n = numbers.get(i); for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j)); ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial); partial_rec.add(n); sum_up_recursive(remaining,target,partial_rec); } } static void sum_up(ArrayList<Integer> numbers, int target) { sum_up_recursive(numbers,target,new ArrayList<Integer>()); } public static void main(String args[]) { Integer[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target); } }

这是完全相同的启发式。我的Java有点生疏，但我觉得很容易理解。

Java解决scheme的C＃转换:( 由@JeremyThompson提供）

 public static void Main(string[] args) { List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 }; int target = 15; sum_up(numbers, target); } private static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers, target, new List<int>()); } private static void sum_up_recursive(List<int> numbers, int target, List<int> partial) { int s = 0; foreach (int x in partial) s += x; if (s == target) Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target); if (s >= target) return; for (int i = 0; i < numbers.Count; i++) { List<int> remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]); List<int> partial_rec = new List<int>(partial); partial_rec.Add(n); sum_up_recursive(remaining, target, partial_rec); } }

Ruby解决scheme:( 通过@emaillenin）

 def subset_sum(numbers, target, partial=[]) s = partial.inject 0, :+ # check if the partial sum is equals to target puts "sum(#{partial})=#{target}" if s == target return if s >= target # if we reach the number why bother to continue (0..(numbers.length - 1)).each do |i| n = numbers[i] remaining = numbers.drop(i+1) subset_sum(remaining, target, partial + [n]) end end subset_sum([3,9,8,4,5,7,10],15)

编辑：复杂性讨论

正如其他人所说，这是一个NP难题。它可以在指数时间O（2 ^ n）中求解，例如对于n = 10，将有1024个可能的解。如果你想要达到的目标是在一个较低的范围内，那么这个algorithm的工作原理。举个例子：

subset_sum([1,2,3,4,5,6,7,8,9,10],100000)生成1024个分支，因为目标永远不会过滤出可能的解决scheme。

另一方面， subset_sum([1,2,3,4,5,6,7,8,9,10],10)只产生了175个分支，因为达到10的目标会过滤掉很多组合。

如果N和Target是大数字，则应该转换为解决scheme的近似版本。

在Haskell中：

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

和J ：

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

您可能会注意到，两者都采用相同的方法，将问题分为两部分：生成权力集合中的每个成员，并检查每个成员的总和。

还有其他的解决scheme，但这是最直接的。

你们是否需要帮助，或者find不同的方法？

这个问题的解决方法已经在互联网上得到了一百万次。这个问题被称为硬币改变问题 。可以在http://rosqtacode.org/wiki/Count_the_coinsfind解决scheme，并在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf （或Google 硬币更改问题 ）。

顺便说一句，Tsagadai的Scala解决scheme很有趣。这个例子产生1或0.作为副作用，它在控制台上列出了所有可能的解决scheme。它显示解决scheme，但无法以任何方式使用。

为了尽可能有用，代码应该返回一个List[List[Int]] ，以便获得解决scheme的数量（列表的长度），“最佳”解决scheme（最短列表）或全部可能的解决scheme。

这是一个例子。这是非常低效的，但很容易理解。

 object Sum extends App { def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = { def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = { (x._1 + y._1, x._2 ::: y._2) } def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = { if (numbers.isEmpty || total < 0) { (0, resultAcc) } else if (total == 0) { (1, sumAcc :: resultAcc) } else { add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers)) } } sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2 } println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n") }

运行时，显示：

 List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2) List(1, 1, 1, 2, 2, 2, 2, 2, 2) List(1, 2, 2, 2, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5) List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5) List(1, 1, 1, 1, 1, 1, 2, 2, 5) List(1, 1, 1, 1, 2, 2, 2, 5) List(1, 1, 2, 2, 2, 2, 5) List(2, 2, 2, 2, 2, 5) List(1, 1, 1, 1, 1, 5, 5) List(1, 1, 1, 2, 5, 5) List(1, 2, 2, 5, 5) List(5, 5, 5) List(1, 1, 1, 1, 1, 10) List(1, 1, 1, 2, 10) List(1, 2, 2, 10) List(5, 10)

sumCombinations()函数本身可以使用，并且可以进一步分析结果以显示“最佳”解决scheme（最短列表）或解决scheme的数目（列表数目）。

请注意，即使这样，要求可能不完全满足。可能发生的问题是解决scheme中每个列表的顺序都很重要。在这种情况下，每个列表都必须复制尽可能多的时间，因为它们的元素组合在一起。或者我们可能只对不同的组合感兴趣。

例如，我们可以认为List(5, 10)应该给出两个组合： List(5, 10)和List(10, 5) 。对于List(5, 5, 5)它可以给出三种组合或只有一种，这取决于要求。对于整数，这三个排列是等价的，但如果我们正在处理硬币，就像在“硬币转换问题”中那样，它们不是。

在要求中也没有规定每个数字（或硬币）是否只能使用一次或多次的问题。我们可以（也应该）将问题概括为每个数字出现的列表。这在现实生活中转化为“用一套硬币（而不是一套硬币值）来赚取一定数量的金钱的可能方式”。原来的问题只是这个问题的一个特例，在这个问题中，我们每个硬币的出现次数与每个硬币的总金额一样多。

一个Javascript版本：

 function subsetSum(numbers, target, partial) { var s, n, remaining; partial = partial || []; // sum partial s = partial.reduce(function (a, b) { return a + b; }, 0); // check if the partial sum is equals to target if (s === target) { console.log("%s=%s", partial.join("+"), target) } if (s >= target) { return; // if we reach the number why bother to continue } for (var i = 0; i < numbers.length; i++) { n = numbers[i]; remaining = numbers.slice(i + 1); subsetSum(remaining, target, partial.concat([n])); } } subsetSum([3,9,8,4,5,7,10],15); // output: // 3+8+4=15 // 3+5+7=15 // 8+7=15 // 5+10=15

C＃版本的@msalvadores代码的答案

 void Main() { int[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new List<int>(numbers.ToList()),target); } static void sum_up_recursive(List<int> numbers, int target, List<int> part) { int s = 0; foreach (int x in part) { s += x; } if (s == target) { Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target); } if (s >= target) { return; } for (int i = 0;i < numbers.Count;i++) { var remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count;j++) { remaining.Add(numbers[j]); } var part_rec = new List<int>(part); part_rec.Add(n); sum_up_recursive(remaining,target,part_rec); } } static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers,target,new List<int>()); }

C ++版本的algorithm相同

 #include <iostream> #include <list> void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial) { int s = 0; for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++) { s += *cit; } if(s == target) { std::cout << "sum(["; for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++) { std::cout << *cit << ","; } std::cout << "])=" << target << std::endl; } if(s >= target) return; int n; for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++) { n = *ai; std::list<int> remaining; for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++) { if(aj == ai)continue; remaining.push_back(*aj); } std::list<int> partial_rec=partial; partial_rec.push_back(n); subset_sum_recursive(remaining,target,partial_rec); } } void subset_sum(std::list<int> numbers,int target) { subset_sum_recursive(numbers,target,std::list<int>()); } int main() { std::list<int> a; a.push_back (3); a.push_back (9); a.push_back (8); a.push_back (4); a.push_back (5); a.push_back (7); a.push_back (10); int n = 15; //std::cin >> n; subset_sum(a, n); return 0; }

我以为我会用这个问题的答案，但我不能，所以这是我的答案。它在计算机程序的结构和解释中使用了一个修改后的答案。我认为这是一个更好的recursion解决scheme，应该让纯粹主义者更多。

我的答案是在斯卡拉（如果我的斯卡拉糟糕，我刚刚开始学习它）道歉。 findSumCombinations疯狂是sorting和唯一的recursion原始列表，以防止愚蠢。

 def findSumCombinations(target: Int, numbers: List[Int]): Int = { cc(target, numbers.distinct.sortWith(_ < _), List()) } def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = { if (target == 0) {println(solution); 1 } else if (target < 0 || numbers.length == 0) 0 else cc(target, numbers.tail, solution) + cc(target - numbers.head, numbers, numbers.head :: solution) }

要使用它：

  > findSumCombinations(12345, List(1,5,22,15,0,..)) * Prints a whole heap of lists that will sum to the target *

 Thank you.. ephemient

我已经转换上面的逻辑从Python到PHP ..

 <?php $data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5)); $maxsum = 25; print_r(bestsum($data,$maxsum)); //function call function bestsum($data,$maxsum) { $res = array_fill(0, $maxsum + 1, '0'); $res[0] = array(); //base case foreach($data as $group) { $new_res = $res; //copy res foreach($group as $ele) { for($i=0;$i<($maxsum-$ele+1);$i++) { if($res[$i] != 0) { $ele_index = $i+$ele; $new_res[$ele_index] = $res[$i]; $new_res[$ele_index][] = $ele; } } } $res = $new_res; } for($i=$maxsum;$i>0;$i--) { if($res[$i]!=0) { return $res[$i]; break; } } return array(); } ?>

要find使用Excel的组合 – （它相当容易）。（你电脑一定不要太慢）

去这个网站
转到“求和到目标”页面
下载“Sum to Target”excel文件。

按照网站页面上的指示。

希望这可以帮助。

当复杂度O(t*N) （dynamic解）大于指数algorithm时，这是一个非常适合小N和非常大目标总和的Java版本。我的版本在中间攻击中使用了一个会面，以及一点点的移动，以便从经典的朴素O(n*2^n)到O(2^(n/2))减less复杂性。

如果要使用32到64个元素的集合，则应该将代表当前子集的int更改为int ，但随着集合大小的增加，性能将显着急剧下降。如果你想使用这个为奇数元素的集合，你应该添加一个0到集合使其偶数。

 import java.util.ArrayList; import java.util.List; public class SubsetSumMiddleAttack { static final int target = 100000000; static final int[] set = new int[]{ ... }; static List<Subset> evens = new ArrayList<>(); static List<Subset> odds = new ArrayList<>(); static int[][] split(int[] superSet) { int[][] ret = new int[2][superSet.length / 2]; for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i]; return ret; } static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) { accumulator.add(new Subset(subset, sum)); if (counter != superSet.length) { step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1); step(superSet, accumulator, subset, sum, counter + 1); } } static void printSubset(Subset e, Subset o) { String ret = ""; for (int i = 0; i < 32; i++) { if (i % 2 == 0) { if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i]; } else { if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i]; } } if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum); System.out.println(ret); } public static void main(String[] args) { int[][] superSets = split(set); step(superSets[0], evens, 0,0,0); step(superSets[1], odds, 0,0,0); for (Subset e : evens) { for (Subset o : odds) { if (e.sum + o.sum == target) printSubset(e, o); } } } } class Subset { int subset; int sum; Subset(int subset, int sum) { this.subset = subset; this.sum = sum; } }

这与硬币更换问题类似

 public class CoinCount { public static void main(String[] args) { int[] coins={1,4,6,2,3,5}; int count=0; for (int i=0;i<coins.length;i++) { count=count+Count(9,coins,i,0); } System.out.println(count); } public static int Count(int Sum,int[] coins,int index,int curSum) { int count=0; if (index>=coins.length) return 0; int sumNow=curSum+coins[index]; if (sumNow>Sum) return 0; if (sumNow==Sum) return 1; for (int i= index+1;i<coins.length;i++) count+=Count(Sum,coins,i,sumNow); return count; } }

非常有效的algorithm使用表格我写在C ++几年前的情侣。

如果你设置PRINT 1，它将打印所有的组合（但是它不会使用有效的方法）。

它的效率很高，可以在10ms内计算10 ^ 14个以上的组合。

 #include <stdio.h> #include <stdlib.h> //#include "CTime.h" #define SUM 300 #define MAXNUMsSIZE 30 #define PRINT 0 long long CountAddToSum(int,int[],int,const int[],int); void printr(const int[], int); long long table1[SUM][MAXNUMsSIZE]; int main() { int Nums[]={3,4,5,6,7,9,13,11,12,13,22,35,17,14,18,23,33,54}; int sum=SUM; int size=sizeof(Nums)/sizeof(int); int i,j,a[]={0}; long long N=0; //CTime timer1; for(i=0;i<SUM;++i) for(j=0;j<MAXNUMsSIZE;++j) table1[i][j]=-1; N = CountAddToSum(sum,Nums,size,a,0); //algorithm //timer1.Get_Passd(); //printf("\nN=%lld time=%.1f ms\n", N,timer1.Get_Passd()); printf("\nN=%lld \n", N); getchar(); return 1; } long long CountAddToSum(int s, int arr[],int arrsize, const int r[],int rsize) { static int totalmem=0, maxmem=0; int i,*rnew; long long result1=0,result2=0; if(s<0) return 0; if (table1[s][arrsize]>0 && PRINT==0) return table1[s][arrsize]; if(s==0) { if(PRINT) printr(r, rsize); return 1; } if(arrsize==0) return 0; //else rnew=(int*)malloc((rsize+1)*sizeof(int)); for(i=0;i<rsize;++i) rnew[i]=r[i]; rnew[rsize]=arr[arrsize-1]; result1 = CountAddToSum(s,arr,arrsize-1,rnew,rsize); result2 = CountAddToSum(s-arr[arrsize-1],arr,arrsize,rnew,rsize+1); table1[s][arrsize]=result1+result2; free(rnew); return result1+result2; } void printr(const int r[], int rsize) { int lastr=r[0],count=0,i; for(i=0; i<rsize;++i) { if(r[i]==lastr) count++; else { printf(" %d*%d ",count,lastr); lastr=r[i]; count=1; } } if(r[i-1]==lastr) printf(" %d*%d ",count,lastr); printf("\n"); }

另一个python解决scheme是使用itertools.combinations模块，如下所示：

 #!/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)]

Swift 3转换Java解决scheme：（by @JeremyThompson）

 protocol _IntType { } extension Int: _IntType {} extension Array where Element: _IntType { func subsets(to: Int) -> [[Element]]? { func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) { var sum: Int = 0 for x in partial { sum += x as! Int } if sum == target { solution.append(partial) } guard sum < target else { return } for i in stride(from: 0, to: numbers.count, by: 1) { var remaining = [Element]() for j in stride(from: i + 1, to: numbers.count, by: 1) { remaining.append(numbers[j]) } var partial_rec = [Element](partial) partial_rec.append(numbers[i]) sum_up_recursive(remaining, target, partial_rec, &solution) } } var solutions = [[Element]]() sum_up_recursive(self, to, [Element](), &solutions) return solutions.count > 0 ? solutions : nil } }

用法：

 let numbers = [3, 9, 8, 4, 5, 7, 10] if let solution = numbers.subsets(to: 15) { print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]] } else { print("not possible") }

这也可以用来打印所有的答案

 public void recur(int[] a, int n, int sum, int[] ans, int ind) { if (n < 0 && sum != 0) return; if (n < 0 && sum == 0) { print(ans, ind); return; } if (sum >= a[n]) { ans[ind] = a[n]; recur(a, n - 1, sum - a[n], ans, ind + 1); } recur(a, n - 1, sum, ans, ind); } public void print(int[] a, int n) { for (int i = 0; i < n; i++) System.out.print(a[i] + " "); System.out.println(); }

时间复杂度是指数的。 2 ^ n的顺序

我正在做一个类似的Scala任务。想在这里发布我的解决scheme：

  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) }

这是一个更好的版本，具有更好的输出格式和C ++ 11function：

 void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) { int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0); if (currentSum > target) return; if (currentSum == target) { std::cout << "sum(["; for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it) cout << *it << ","; cout << *std::prev(partialNums.end()); std::cout << "])=" << target << std::endl; } for (auto it = nums.begin(); it != nums.end(); ++it) { std::vector<int> remaining; for (auto it2 = std::next(it); it2 != nums.end(); ++it2) remaining.push_back(*it2); std::vector<int> partial = partialNums; partial.push_back(*it); subset_sum_rec(remaining, target, partial); } }

这是R的解决scheme

 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)) } }

Excel VBA版本如下。我需要在VBA中实现这个（不是我的偏好，不要评价我！），并在这个页面上使用了答案。我正在上传，以防其他人也需要VBA版本。

 Option Explicit Public Sub SumTarget() Dim numbers(0 To 6) As Long Dim target As Long target = 15 numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5 numbers(5) = 7: numbers(6) = 10 Call SumUpTarget(numbers, target) End Sub Public Sub SumUpTarget(numbers() As Long, target As Long) Dim part() As Long Call SumUpRecursive(numbers, target, part) End Sub Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long) Dim s As Long, i As Long, j As Long, num As Long Dim remaining() As Long, partRec() As Long s = SumArray(part) If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target If s >= target Then Exit Sub If (Not Not numbers) <> 0 Then For i = 0 To UBound(numbers) Erase remaining() num = numbers(i) For j = i + 1 To UBound(numbers) AddToArray remaining, numbers(j) Next j Erase partRec() CopyArray partRec, part AddToArray partRec, num SumUpRecursive remaining, target, partRec Next i End If End Sub Private Function ArrayToString(x() As Long) As String Dim n As Long, result As String result = "{" & x(n) For n = LBound(x) + 1 To UBound(x) result = result & "," & x(n) Next n result = result & "}" ArrayToString = result End Function Private Function SumArray(x() As Long) As Long Dim n As Long SumArray = 0 If (Not Not x) <> 0 Then For n = LBound(x) To UBound(x) SumArray = SumArray + x(n) Next n End If End Function Private Sub AddToArray(arr() As Long, x As Long) If (Not Not arr) <> 0 Then ReDim Preserve arr(0 To UBound(arr) + 1) Else ReDim Preserve arr(0 To 0) End If arr(UBound(arr)) = x End Sub Private Sub CopyArray(destination() As Long, source() As Long) Dim n As Long If (Not Not source) <> 0 Then For n = 0 To UBound(source) AddToArray destination, source(n) Next n End If End Sub

输出（写入立即窗口）应该是：

 SUM ( {3,8,4} ) = 15 SUM ( {3,5,7} ) = 15 SUM ( {8,7} ) = 15 SUM ( {5,10} ) = 15

我将C＃示例移植到了Objective-c中，但没有在响应中看到它：

 //Usage NSMutableArray* numberList = [[NSMutableArray alloc] init]; NSMutableArray* partial = [[NSMutableArray alloc] init]; int target = 16; for( int i = 1; i<target; i++ ) { [numberList addObject:@(i)]; } [self findSums:numberList target:target part:partial]; //******************************************************************* // Finds combinations of numbers that add up to target recursively //******************************************************************* -(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial { int s = 0; for (NSNumber* x in partial) { s += [x intValue]; } if (s == target) { NSLog(@"Sum[%@]", partial); } if (s >= target) { return; } for (int i = 0;i < [numbers count];i++ ) { int n = [numbers[i] intValue]; NSMutableArray* remaining = [[NSMutableArray alloc] init]; for (int j = i + 1; j < [numbers count];j++) { [remaining addObject:@([numbers[j] intValue])]; } NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial]; [partRec addObject:@(n)]; [self findSums:remaining target:target part:partRec]; } }

@ KeithBeller的答案略有改变的variables名称和一些意见。

  public static void Main(string[] args) { List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 }; int targetSum = 15; SumUp(input, targetSum); } public static void SumUp(List<int> input, int targetSum) { SumUpRecursive(input, targetSum, new List<int>()); } private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum) { // Sum up partial int sum = 0; foreach (int x in listToSum) sum += x; //Check sum matched if (sum == targetSum) Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum); //Check sum passed if (sum >= targetSum) return; //Iterate each input character for (int i = 0; i < remaining.Count; i++) { //Build list of remaining items to iterate List<int> newRemaining = new List<int>(); for (int j = i + 1; j < remaining.Count; j++) newRemaining.Add(remaining[j]); //Update partial list List<int> newListToSum = new List<int>(listToSum); int currentItem = remaining[i]; newListToSum.Add(currentItem); SumUpRecursive(newRemaining, targetSum, newListToSum); } }'

PHP版本 ，由基思贝勒的C＃版本启发。

巴拉的PHP版本不适合我，因为我不需要分组号码。我想要一个更简单的实现，一个目标值和一个数字池。这个函数也会修剪任何重复的条目。

 /** * Calculates a subset sum: finds out which combinations of numbers * from the numbers array can be added together to come to the target * number. * * Returns an indexed array with arrays of number combinations. * * Example: * * <pre> * $matches = subset_sum(array(5,10,7,3,20), 25); * </pre> * * Returns: * * <pre> * Array * ( * [0] => Array * ( * [0] => 3 * [1] => 5 * [2] => 7 * [3] => 10 * ) * [1] => Array * ( * [0] => 5 * [1] => 20 * ) * ) * </pre> * * @param number[] $numbers * @param number $target * @param array $part * @return array[number[]] */ function subset_sum($numbers, $target, $part=null) { // we assume that an empty $part variable means this // is the top level call. $toplevel = false; if($part === null) { $toplevel = true; $part = array(); } $s = 0; foreach($part as $x) { $s = $s + $x; } // we have found a match! if($s == $target) { sort($part); // ensure the numbers are always sorted return array(implode('|', $part)); } // gone too far, break off if($s >= $target) { return null; } $matches = array(); $totalNumbers = count($numbers); for($i=0; $i < $totalNumbers; $i++) { $remaining = array(); $n = $numbers[$i]; for($j = $i+1; $j < $totalNumbers; $j++) { $remaining[] = $numbers[$j]; } $part_rec = $part; $part_rec[] = $n; $result = subset_sum($remaining, $target, $part_rec); if($result) { $matches = array_merge($matches, $result); } } if(!$toplevel) { return $matches; } // this is the top level function call: we have to // prepare the final result value by stripping any // duplicate results. $matches = array_unique($matches); $result = array(); foreach($matches as $entry) { $result[] = explode('|', $entry); } return $result; }

find所有可能的数字组合，以达到给定的总和

PHP数组组合

生成vector元素的所有可能组合的列表

用python重复生成排列

Google采访：块的安排

应用程序体系结构/在F＃

PHP：如何获得一维数组的所有可能的组合？

嵌套循环的更快替代？

协会vs组合vs协会vs直接协会

JavaScript – 从m个元素生成n个数组的组合

成分路线背后的“大创意”是什么？