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

func sum(array : [Int]) -> Int{
    var sum = 0
    array.forEach { (item) in
        sum = item + sum
    }
    return sum
}
func susetNumbers(array :[Int], target : Int, subsetArray: [Int],result : inout [[Int]]) -> [[Int]]{
    let s = sum(array: subsetArray)
    if(s == target){
        print("sum\(subsetArray) = \(target)")
        result.append(subsetArray)
    }
    for i in 0..<array.count{
        let n = array[i]
        let remaning = Array(array[(i+1)..<array.count])
        susetNumbers(array: remaning, target: target, subsetArray: subsetArray + [n], result: &result)
        
    }
    return result
}

 var resultArray = [[Int]]()
    let newA = susetNumbers(array: [1,2,3,4,5], target: 5, subsetArray: [],result:&resultArray)
    print(resultArray)

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

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

我将c#示例移植到Objective-c，并没有在响应中看到它:

//Usage
NSMutableArray* numberList = [[NSMutableArray alloc] init];
NSMutableArray* partial = [[NSMutableArray alloc] init];
int target = 16;
for( int i = 1; i<target; i++ )
{ [numberList addObject:@(i)]; }
[self findSums:numberList target:target part:partial];


//*******************************************************************
// Finds combinations of numbers that add up to target recursively
//*******************************************************************
-(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial
{
    int s = 0;
    for (NSNumber* x in partial)
    { s += [x intValue]; }

    if (s == target)
    { NSLog(@"Sum[%@]", partial); }

    if (s >= target)
    { return; }

    for (int i = 0;i < [numbers count];i++ )
    {
        int n = [numbers[i] intValue];
        NSMutableArray* remaining = [[NSMutableArray alloc] init];
        for (int j = i + 1; j < [numbers count];j++)
        { [remaining addObject:@([numbers[j] intValue])]; }

        NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
        [partRec addObject:@(n)];
        [self findSums:remaining target:target part:partRec];
    }
}

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

}

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