function solve(n){
    let DP = [];

     DP[0] = DP[1] = DP[2] = 1;
     DP[3] = 2;

    for (let i = 4; i <= n; i++) {
      DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
    }
    return DP[n]
}

console.log(solve(5))

这是JS的一个动态解决方案，告诉任何人有多少种方法可以得到一定的总和。如果考虑到时间和空间的复杂性，这可能是正确的解决方案。

这是R中的一个解

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}

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

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

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

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

非常有效的算法，使用我几年前用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");

}