这个问题可以通过所有可能的和的递归组合来解决，过滤掉那些达到目标的和。下面是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

这种类型的算法在接下来的斯坦福大学抽象编程课程中有很好的解释-这个视频非常推荐来理解递归是如何产生解决方案的排列的。

Edit

上面作为一个生成器函数，使它更有用一点。需要Python 3.3+，因为yield来自。

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#转换(by @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解决方案:(by @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个可能的解。如果你要达到的目标是在一个较低的范围内，那么这个算法是有效的。例如:

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

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

如果N和目标都是很大的数字，那么就应该得到近似的解。

我不喜欢上面看到的Javascript解决方案。下面是我使用部分应用、闭包和递归构建的一个:

好的，我主要关心的是，如果组合数组能满足目标要求，希望这样你就能找到剩下的组合了

这里只需要设置目标并传递组合数组。

function main() {
    const target = 10
    const getPermutationThatSumT = setTarget(target)
    const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])

    console.log( permutation );
}

我提出的当前实现

function setTarget(target) {
    let partial = [];

    return function permute(input) {
        let i, removed;
        for (i = 0; i < input.length; i++) {
            removed = input.splice(i, 1)[0];
            partial.push(removed);

            const sum = partial.reduce((a, b) => a + b)
            if (sum === target) return partial.slice()
            if (sum < target) permute(input)

            input.splice(i, 0, removed);
            partial.pop();
        }
        return null
    };
}

用excel找到组合(相当容易)。 (你的电脑不能太慢)

去这个网站 进入“Sum to Target”页面 下载“Sum to Target”excel文件。 按照网站页面上的说明操作。

希望这能有所帮助。

我想我应该用这个问题的答案，但我不能，所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解，应该更能取悦纯粹主义者。

我的答案是用Scala(如果我的Scala很烂，我很抱歉，我刚刚开始学习)。findsumcombination的疯狂之处在于对递归的原始列表进行排序和惟一，以防止欺骗。

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 *

@KeithBeller的回答略有变化的变量名称和一些评论。

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

另一个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)]