非常有效的算法，使用我几年前用c++写的表格。

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

它非常高效，在不到10毫秒的时间内计算了超过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");

}

PHP版本，灵感来自Keith Beller的c#版本。

bala的PHP版本不适合我，因为我不需要对数字进行分组。我想要一个更简单的实现，只有一个目标值和一个数字池。这个函数也会删除任何重复的条目。

编辑25/10/2021:添加精度参数以支持浮点数(现在需要bcmath扩展)。

/**
 * 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
 * @param int $precision
 * @return array[number[]]
 */
function subset_sum($numbers, $target, $precision=0, $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(bccomp((string) $s, (string) $target, $precision) === 0)
    {
        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, $precision, $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;
}

例子:

$result = subset_sum(array(5, 10, 7, 3, 20), 25);

这将返回一个包含两个数字组合数组的索引数组:

3, 5, 7, 10
5, 20

浮点数示例:

// Specify the precision in the third argument
$result = subset_sum(array(0.40, 0.03, 0.05), 0.45, 2);

这将返回一个匹配项:

0.40, 0.05

我不喜欢上面看到的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
    };
}

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

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

我的答案是用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 *

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

这里的解决方案是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))是所有使用任意索引到达目标的解。这就是我们想要的。