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

在Haskell:

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

J:

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

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

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

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

这个问题的一个迭代c++堆栈解决方案。与其他迭代解决方案不同的是，它不会对中间序列进行不必要的复制。

#include <vector>
#include <iostream>

// Given a positive integer, return all possible combinations of
// positive integers that sum up to it.

std::vector<std::vector<int>> print_all_sum(int target){
    std::vector<std::vector<int>> output;
    std::vector<int> stack;

    int curr_min = 1;
    int sum = 0;
    while (curr_min < target) {
        sum += curr_min;
        if (sum >= target) {
            if (sum == target) {
                output.push_back(stack); // make a copy
                output.back().push_back(curr_min);
            }
            sum -= curr_min + stack.back();
            curr_min = stack.back() + 1;
            stack.pop_back();
        } else {
            stack.push_back(curr_min);
        }
    }

    return output;
}

int main()
{
    auto vvi = print_all_sum(6);

    for (auto const& v: vvi) {
        for(auto const& i: v) {
        std::cout << i;
        }
        std::cout << "\n";
    }

    return 0;
}

输出print_all_sum (6):

111111
11112
1113
1122
114
123
15
222
24
33

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

}

下面是一个更好的版本，具有更好的输出格式和c++ 11特性:

void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) 
{
    int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
    if (currentSum > target)
        return;
    if (currentSum == target) 
    {
        std::cout << "sum([";
        for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
            cout << *it << ",";
        cout << *std::prev(partialNums.end());
        std::cout << "])=" << target << std::endl;
    }
    for (auto it = nums.begin(); it != nums.end(); ++it) 
    {
        std::vector<int> remaining;
        for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
            remaining.push_back(*it2);

        std::vector<int> partial = partialNums;
        partial.push_back(*it);
        subset_sum_rec(remaining, target, partial);
    }
}

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