import java.util.*;

public class Main{

     int recursionDepth = 0;
     private int[][] memo;

     public static void main(String []args){
         int[] nums = new int[] {5,2,4,3,1};
         int N = nums.length;
         Main main =  new Main();
         main.memo = new int[N+1][N+1];
         main._findCombo(0, N-1,nums, 8, 0, new LinkedList() );
         System.out.println(main.recursionDepth);
     }


       private void _findCombo(
           int from,
           int to,
           int[] nums,
           int targetSum,
           int currentSum,
           LinkedList<Integer> list){

            if(memo[from][to] != 0) {
                currentSum = currentSum + memo[from][to];
            }

            if(currentSum > targetSum) {
                return;
            }

            if(currentSum ==  targetSum) {
                System.out.println("Found - " +list);
                return;
            }

            recursionDepth++;

           for(int i= from ; i <= to; i++){
               list.add(nums[i]);
               memo[from][i] = currentSum + nums[i];
               _findCombo(i+1, to,nums, targetSum, memo[from][i], list);
                list.removeLast();
           }

     }
}

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

建议回答:

下面是一个使用es2015生成器的解决方案:

function* subsetSum(numbers, target, partial = [], partialSum = 0) {

  if(partialSum === target) yield partial

  if(partialSum >= target) return

  for(let i = 0; i < numbers.length; i++){
    const remaining = numbers.slice(i + 1)
        , n = numbers[i]

    yield* subsetSum(remaining, target, [...partial, n], partialSum + n)
  }

}

使用生成器实际上非常有用，因为它允许您在找到有效子集时立即暂停脚本执行。这与没有生成器(即缺乏状态)的解决方案形成对比，后者必须遍历每个数字子集

@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)]

这个问题的解决方案在互联网上已经出现过无数次了。这个问题叫做硬币兑换问题。你可以在http://rosettacode.org/wiki/Count_the_coins上找到答案，在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf上找到数学模型(或谷歌硬币变化问题)。

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

为了尽可能有用，代码应该返回一个List[List[Int]]，以允许获得解决方案的数量(列表列表的长度)，“最佳”解决方案(最短的列表)，或所有可能的解决方案。

这里有一个例子。它效率很低，但很容易理解。

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)

sumcombination()函数可以单独使用，并且可以进一步分析结果以显示“最佳”解决方案(最短的列表)或解决方案的数量(列表的数量)。

请注意，即使这样，需求也可能无法完全满足。解决方案中每个列表的顺序可能是重要的。在这种情况下，每个列表都必须重复它的元素组合的次数。或者我们只对不同的组合感兴趣。

例如，我们可以考虑List(5,10)应该给出两种组合:List(5,10)和List(10,5)。对于List(5,5,5)，它可以给出三种组合，也可以只给出一种组合，这取决于需求。对于整数，这三种排列是等价的，但如果我们处理的是硬币，就像在“硬币更换问题”中一样，它们就不一样了。

Also not stated in the requirements is the question of whether each number (or coin) may be used only once or many times. We could (and we should!) generalize the problem to a list of lists of occurrences of each number. This translates in real life into "what are the possible ways to make an certain amount of money with a set of coins (and not a set of coin values)". The original problem is just a particular case of this one, where we have as many occurrences of each coin as needed to make the total amount with each single coin value.