这个问题的一个迭代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

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)

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

用excel找到组合(相当容易)。 (你的电脑不能太慢)

去这个网站 进入“Sum to Target”页面 下载“Sum to Target”excel文件。 按照网站页面上的说明操作。

希望这能有所帮助。

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

我将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];
    }
}