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

可以通过将所有可能的总和的递归组合过滤掉达到目标的总和来解决此问题。这是Python中的算法：

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

在以下Standford的Abstract
Programming演讲
中，很好地解释了这种算法-
该视频非常可取，以了解递归如何工作以生成解的置换。

编辑

上面作为生成器函数，使其更加有用。由于，需要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)

这是相同算法的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解决方案的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解决方案：（ 通过@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])  endendsubset_sum([3,9,8,4,5,7,10],15)

编辑：复杂性讨论

正如其他人所提到的，这是一个NP难题。可以在指数时间O（2
^ n）中求解，例如对于n = 10，将有1024个可能的解。如果您要达到的目标范围较小，则此算法有效。因此，例如：

subset_sum([1,2,3,4,5,6,7,8,9,10],100000)

另一方面，

subset_sum([1,2,3,4,5,6,7,8,9,10],10)

10

如果

N

Target