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

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();
}
?>

下面是一个Java版本，它非常适合小N和非常大的目标和，当复杂度O(t*N)(动态解)大于指数算法时。我的版本在中间攻击中使用了一个meet，并进行了一些调整，以降低复杂度，从经典的naive O(n*2^n)降低到O(2^(n/2))。

如果你想在32到64个元素之间的集合中使用这种方法，你应该将表示step函数中当前子集的int改为long，尽管随着集合大小的增加，性能显然会急剧下降。如果你想对一个有奇数个元素的集合使用这个，你应该给这个集合加上一个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;
    }
}

这个问题可以通过所有可能的和的递归组合来解决，过滤掉那些达到目标的和。下面是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和目标都是很大的数字，那么就应该得到近似的解。

到目前为止，有很多解决方案，但都是生成然后过滤的形式。这意味着他们可能会在递归路径上花费大量时间，而这些递归路径不会导致解决方案。

这里的解决方案是O(size_of_array * (number_of_sum + number_of_solutions))。换句话说，它使用动态规划来避免列举永远不会匹配的可能解决方案。

为了搞笑，我让这个函数同时使用正数和负数，并让它成为一个迭代器。它适用于Python 2.3+。

def subset_sum_iter(array, target):
    sign = 1
    array = sorted(array)
    if target < 0:
        array = reversed(array)
        sign = -1
    # Checkpoint A

    last_index = {0: [-1]}
    for i in range(len(array)):
        for s in list(last_index.keys()):
            new_s = s + array[i]
            if 0 < (new_s - target) * sign:
                pass # Cannot lead to target
            elif new_s in last_index:
                last_index[new_s].append(i)
            else:
                last_index[new_s] = [i]
    # Checkpoint B

    # Now yield up the answers.
    def recur(new_target, max_i):
        for i in last_index[new_target]:
            if i == -1:
                yield [] # Empty sum.
            elif max_i <= i:
                break # Not our solution.
            else:
                for answer in recur(new_target - array[i], i):
                    answer.append(array[i])
                    yield answer

    for answer in recur(target, len(array)):
        yield answer

这里有一个例子，它与数组和目标一起使用，在其他解决方案中使用的过滤方法实际上永远不会结束。

def is_prime(n):
    for i in range(2, n):
        if 0 == n % i:
            return False
        elif n < i * i:
            return True
    if n == 2:
        return True
    else:
        return False


def primes(limit):
    n = 2
    while True:
        if is_prime(n):
            yield(n)
        n = n + 1
        if limit < n:
            break


for answer in subset_sum_iter(primes(1000), 76000):
    print(answer)

这将在2秒内打印所有522个答案。之前的方法如果能在宇宙当前的生命周期内找到答案，那就太幸运了。(整个空间有2^168 = 3.74144419156711e+50个可能的组合。那需要一段时间。)

解释 我被要求解释代码，但解释数据结构通常更能说明问题。我来解释一下数据结构。

让我们考虑subset_sum_iter([2, 2、3、3、5、5、7、7、-11、11),10)。

在检查点A，我们已经意识到我们的目标是正的，所以符号= 1。我们已经对输入进行了排序，使array =[-11， -7， -5， -3， -2, 2,3,5,7,11]。由于我们经常通过索引访问它，下面是从索引到值的映射:

0: -11
1:  -7
2:  -5
3:  -3
4:  -2
5:   2
6:   3
7:   5
8:   7
9:  11

通过检查点B，我们使用动态规划生成last_index数据结构。它包含什么?

last_index = {    
    -28: [4],
    -26: [3, 5],
    -25: [4, 6],
    -24: [5],
    -23: [2, 4, 5, 6, 7],
    -22: [6],
    -21: [3, 4, 5, 6, 7, 8],
    -20: [4, 6, 7],
    -19: [3, 5, 7, 8],
    -18: [1, 4, 5, 6, 7, 8],
    -17: [4, 5, 6, 7, 8, 9],
    -16: [2, 4, 5, 6, 7, 8],
    -15: [3, 5, 6, 7, 8, 9],
    -14: [3, 4, 5, 6, 7, 8, 9],
    -13: [4, 5, 6, 7, 8, 9],
    -12: [2, 4, 5, 6, 7, 8, 9],
    -11: [0, 5, 6, 7, 8, 9],
    -10: [3, 4, 5, 6, 7, 8, 9],
    -9: [4, 5, 6, 7, 8, 9],
    -8: [3, 5, 6, 7, 8, 9],
    -7: [1, 4, 5, 6, 7, 8, 9],
    -6: [5, 6, 7, 8, 9],
    -5: [2, 4, 5, 6, 7, 8, 9],
    -4: [6, 7, 8, 9],
    -3: [3, 5, 6, 7, 8, 9],
    -2: [4, 6, 7, 8, 9],
    -1: [5, 7, 8, 9],
    0: [-1, 5, 6, 7, 8, 9],
    1: [6, 7, 8, 9],
    2: [5, 6, 7, 8, 9],
    3: [6, 7, 8, 9],
    4: [7, 8, 9],
    5: [6, 7, 8, 9],
    6: [7, 8, 9],
    7: [7, 8, 9],
    8: [7, 8, 9],
    9: [8, 9],
    10: [7, 8, 9]
}

(旁注，它不是对称的，因为条件if 0 < (new_s - target) *符号阻止我们记录超过target的任何内容，在我们的例子中是10。)

这是什么意思?以条目10为例:[7,8,9]。这意味着我们可以得到10的最终和，最后选择的数字在索引7、8或9处。也就是说，最后选择的数字可以是5,7或11。

让我们仔细看看如果我们选择索引7会发生什么。这意味着我们以5结束。因此，在得到下标7之前，我们必须得到10-5 = 5。5的条目为5:[6,7,8,9]。所以我们可以选择指数6，也就是3。虽然我们在第7、8和9处得到了5，但在第7号下标之前我们没有得到5。所以倒数第二个选项是指数6处的3。

现在我们要在下标6之前得到5-3 = 2。条目2是:2:[5,6,7,8,9]。同样，我们只关心下标5的答案因为其他的都发生得太晚了。所以倒数第三个选项是指数5处的2。

最后我们要在下标5之前得到2-2 = 0。条目0表示:0:[- 1,5,6,7,8,9]。同样，我们只关心-1。但是-1不是下标实际上我用它来表示我们已经完成了选择。

我们求出了2+3+5 = 10的解。这是我们打印出来的第一个解。

现在我们来看递归子函数。因为它是在main函数内部定义的，所以它可以看到last_index。

首先要注意的是，它调用的是yield，而不是return。这使它成为一个发电机。当你调用它时，你会返回一个特殊类型的迭代器。当你循环遍历那个迭代器时，你会得到一个它能产生的所有东西的列表。但你是在生成它们时得到它们的。如果它是一个很长的列表，你不把它放在内存中。(有点重要，因为我们可以得到一个很长的列表。)

recur(new_target, max_i)将产生的结果是你可以用数组中最大索引为max_i的元素求和为new_target的所有方法。这就是它的答案:“我们必须在索引max_i+1之前到达new_target。”当然，它是递归的。

因此，recur(target, len(array))是所有使用任意索引到达目标的解。这就是我们想要的。

在Haskell:

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

J:

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

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

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

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