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

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

首先推导0。0是加法的一个恒等式所以在这个特殊情况下，它在单类定律下是没有用的。如果你想向上爬到一个正数，也可以推导出负数。否则还需要做减法运算。

所以…在这个特定的作业中，你能得到的最快算法如下所示。

函数items2T ([n,……ns), t) { Var c = ~~(t/n); 返回ns。长度呢?数组(c + 1) .fill () .reduce((r，_，i) => r.concat(items2T(ns, t-n*i)。map(s => Array(i).fill(n).concat(s)))，[]) : t % n ?［］ :[数组(c) .fill (n)); }; Var数据= [3,9,8,4,5,7,10]， 结果; console.time(“组合”); result = items2T(data, 15); console.timeEnd(“组合”); console.log (JSON.stringify(结果));

这是一个非常快的算法，但如果你对数据数组进行降序排序，它会更快。使用.sort()是无关紧要的，因为算法最终会减少递归调用。

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

这类似于硬币更换问题

public class CoinCount 
{   
public static void main(String[] args)
{
    int[] coins={1,4,6,2,3,5};
    int count=0;

    for (int i=0;i<coins.length;i++)
    {
        count=count+Count(9,coins,i,0);
    }
    System.out.println(count);
}

public static int Count(int Sum,int[] coins,int index,int curSum)
{
    int count=0;

    if (index>=coins.length)
        return 0;

    int sumNow=curSum+coins[index];
    if (sumNow>Sum)
        return 0;
    if (sumNow==Sum)
        return 1;

    for (int i= index+1;i<coins.length;i++)
        count+=Count(Sum,coins,i,sumNow);

    return count;       
}
}

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

}

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