求得到给定和的所有可能的数字组合

小开

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

和J:

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

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

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

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

小开

最佳答案

这个问题可以通过所有可能的和的递归组合来解决，过滤掉那些达到目标的和。下面是Python中的算法:

def subset_sum(numbers, target, partial=[]):
s = sum(partial)


# check if the partial sum is equals to target
if s == target:
print "sum(%s)=%s" % (partial, target)
if s >= target:
return  # if we reach the number why bother to continue
    

for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n])
   



if __name__ == "__main__":
subset_sum([3,9,8,4,5,7,10],15)


#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15

这种类型的算法在下面斯坦福大学的抽象编程讲座中有很好的解释-这个视频非常推荐来理解递归是如何产生解决方案的排列的。

编辑

上面作为一个生成器函数，使它更有用一点。因为yield from需要Python 3.3+。

def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

下面是相同算法的Java版本:

package tmp;


import java.util.ArrayList;
import java.util.Arrays;


class SumSet {
static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
int s = 0;
for (int x: partial) s += x;
if (s == target)
System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
if (s >= target)
return;
for(int i=0;i<numbers.size();i++) {
ArrayList<Integer> remaining = new ArrayList<Integer>();
int n = numbers.get(i);
for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
partial_rec.add(n);
sum_up_recursive(remaining,target,partial_rec);
}
}
static void sum_up(ArrayList<Integer> numbers, int target) {
sum_up_recursive(numbers,target,new ArrayList<Integer>());
}
public static void main(String args[]) {
Integer[] numbers = {3,9,8,4,5,7,10};
int target = 15;
sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
}
}

这是完全相同的启发式。我的Java有点生疏，但我认为很容易理解。

c#转换Java解决方案: (通过@JeremyThompson)

public static void Main(string[] args)
{
List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
int target = 15;
sum_up(numbers, target);
}


private static void sum_up(List<int> numbers, int target)
{
sum_up_recursive(numbers, target, new List<int>());
}


private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
int s = 0;
foreach (int x in partial) s += x;


if (s == target)
Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);


if (s >= target)
return;


for (int i = 0; i < numbers.Count; i++)
{
List<int> remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);


List<int> partial_rec = new List<int>(partial);
partial_rec.Add(n);
sum_up_recursive(remaining, target, partial_rec);
}
}

Ruby的解决方案: (通过lenin)

def subset_sum(numbers, target, partial=[])
s = partial.inject 0, :+
# check if the partial sum is equals to target


puts "sum(#{partial})=#{target}" if s == target


return if s >= target # if we reach the number why bother to continue


(0..(numbers.length - 1)).each do |i|
n = numbers[i]
remaining = numbers.drop(i+1)
subset_sum(remaining, target, partial + [n])
end
end


subset_sum([3,9,8,4,5,7,10],15)

编辑:复杂性讨论

正如其他人提到的，这是np难度问题。它可以在O(2^n)的指数时间内求解，例如n=10，将有1024个可能的解。如果你要达到的目标是在一个较低的范围内，那么这个算法是有效的。例如:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000)生成1024个分支，因为目标永远无法过滤出可能的解决方案。

另一方面，subset_sum([1,2,3,4,5,6,7,8,9,10],10)只生成175个分支，因为要到达10的目标必须过滤掉许多组合。

如果N和Target是较大的数字，则应该使用近似的解决方案。

小开

Thank you.. ephemient

我已经将上述逻辑从python转换为php..

<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;


print_r(bestsum($data,$maxsum));  //function call


function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array();              //base case
foreach($data as $group)
{
$new_res = $res;               //copy res


foreach($group as $ele)
{
for($i=0;$i<($maxsum-$ele+1);$i++)
{
if($res[$i] != 0)
{
$ele_index = $i+$ele;
$new_res[$ele_index] = $res[$i];
$new_res[$ele_index][] = $ele;
}
}
}


$res = $new_res;
}


for($i=$maxsum;$i>0;$i--)
{
if($res[$i]!=0)
{
return $res[$i];
break;
}
}
return array();
}
?>

小开

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

小开

另一个python解决方案是使用itertools.combinations模块，如下所示:

#!/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)]

小开

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

我的答案是用Scala(如果我的Scala很烂，我很抱歉，我刚刚开始学习)。findSumCombinations的疯狂之处在于对递归的原始列表进行排序和唯一，以防止欺骗。

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 *

小开

这个问题的解决方案在互联网上已经出现过无数次了。这个问题被称为硬币兑换问题。人们可以在http://rosettacode.org/wiki/Count_the_coins找到解，在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf(或谷歌硬币兑换问题)找到它的数学模型。

顺便说一下，Tsagadai的Scala解决方案很有趣。本例生成1或0。作为一个副作用，它在控制台上列出了所有可能的解决方案。它显示解决方案，但无法以任何方式使其可用。

为了尽可能有用，代码应该返回__abc0，以便允许获得解决方案的数量(列表列表的长度)，“最佳”解决方案(最短的列表)，或所有可能的解决方案。

这里有一个例子。它效率很低，但很容易理解。

object Sum extends App {


def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {


def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
(x._1 + y._1, x._2 ::: y._2)
}


def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
if (numbers.isEmpty || total < 0) {
(0, resultAcc)
} else if (total == 0) {
(1, sumAcc :: resultAcc)
} else {
add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
}
}


sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
}


println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

运行时，它显示:

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

sumCombinations()函数可以单独使用，并且可以进一步分析结果以显示“最佳”解(最短的列表)或解的数量(列表的数量)。

请注意，即使这样，需求也可能无法完全满足。解决方案中每个列表的顺序可能是重要的。在这种情况下，每个列表都必须重复它的元素组合的次数。或者我们只对不同的组合感兴趣。

例如，我们可以考虑List(5, 10)应该给出两个组合:List(5, 10)和List(10, 5)。对于List(5, 5, 5)，它可以给出三种组合，也可以只给出一种组合，这取决于需求。对于整数，这三种排列是等价的，但如果我们处理的是硬币，就像在“硬币更换问题”中一样，它们就不一样了。

要求中也没有说明每个数字(或硬币)只能使用一次还是多次的问题。我们可以(而且应该!)将问题概括为每个数字出现的列表。这在现实生活中转化为“用一套硬币(而不是一套硬币价值)赚一定数量钱的可能方法是什么”。原来的问题只是这个问题的一个特例，每个硬币出现的次数等于每个硬币的总价值。

小开

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

去这个网站
进入“Sum to Target”页面
下载“Sum to Target”excel文件。

.
.
.

希望这能有所帮助。

小开

c++版本的相同算法

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
int s = 0;
for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
{
s += *cit;
}
if(s == target)
{
std::cout << "sum([";


for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
{
std::cout << *cit << ",";
}
std::cout << "])=" << target << std::endl;
}
if(s >= target)
return;
int n;
for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
{
n = *ai;
std::list<int> remaining;
for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
{
if(aj == ai)continue;
remaining.push_back(*aj);
}
std::list<int> partial_rec=partial;
partial_rec.push_back(n);
subset_sum_recursive(remaining,target,partial_rec);


}
}


void subset_sum(std::list<int> numbers,int target)
{
subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
std::list<int> a;
a.push_back (3); a.push_back (9); a.push_back (8);
a.push_back (4);
a.push_back (5);
a.push_back (7);
a.push_back (10);
int n = 15;
//std::cin >> n;
subset_sum(a, n);
return 0;
}

小开

这类似于硬币更换问题

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");


}

小开

Excel VBA版本如下。我需要在VBA中实现这一点(不是我的偏好，不要评判我!)，并使用本页上的答案作为方法。我上传以防其他人也需要VBA版本。

Option Explicit


Public Sub SumTarget()
Dim numbers(0 To 6)  As Long
Dim target As Long


target = 15
numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5
numbers(5) = 7: numbers(6) = 10


Call SumUpTarget(numbers, target)
End Sub


Public Sub SumUpTarget(numbers() As Long, target As Long)
Dim part() As Long
Call SumUpRecursive(numbers, target, part)
End Sub


Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long)


Dim s As Long, i As Long, j As Long, num As Long
Dim remaining() As Long, partRec() As Long
s = SumArray(part)


If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target
If s >= target Then Exit Sub


If (Not Not numbers) <> 0 Then
For i = 0 To UBound(numbers)
Erase remaining()
num = numbers(i)
For j = i + 1 To UBound(numbers)
AddToArray remaining, numbers(j)
Next j
Erase partRec()
CopyArray partRec, part
AddToArray partRec, num
SumUpRecursive remaining, target, partRec
Next i
End If


End Sub


Private Function ArrayToString(x() As Long) As String
Dim n As Long, result As String
result = "{" & x(n)
For n = LBound(x) + 1 To UBound(x)
result = result & "," & x(n)
Next n
result = result & "}"
ArrayToString = result
End Function


Private Function SumArray(x() As Long) As Long
Dim n As Long
SumArray = 0
If (Not Not x) <> 0 Then
For n = LBound(x) To UBound(x)
SumArray = SumArray + x(n)
Next n
End If
End Function


Private Sub AddToArray(arr() As Long, x As Long)
If (Not Not arr) <> 0 Then
ReDim Preserve arr(0 To UBound(arr) + 1)
Else
ReDim Preserve arr(0 To 0)
End If
arr(UBound(arr)) = x
End Sub


Private Sub CopyArray(destination() As Long, source() As Long)
Dim n As Long
If (Not Not source) <> 0 Then
For n = 0 To UBound(source)
AddToArray destination, source(n)
Next n
End If
End Sub

输出(写入立即窗口)应该是:

SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15

小开

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

小开

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

小开

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

小开

这也可以用来打印所有的答案

public void recur(int[] a, int n, int sum, int[] ans, int ind) {
if (n < 0 && sum != 0)
return;
if (n < 0 && sum == 0) {
print(ans, ind);
return;
}
if (sum >= a[n]) {
ans[ind] = a[n];
recur(a, n - 1, sum - a[n], ans, ind + 1);
}
recur(a, n - 1, sum, ans, ind);
}


public void print(int[] a, int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}

时间复杂度是指数级的。2^n的阶

小开

下面是一个Java版本，它非常适合小N和非常大的目标和，当复杂度O(t*N)(动态解)大于指数算法。我的版本在中间攻击中使用了一个meet，并进行了一些调整，以减少从经典的朴素O(n*2^n)到O(2^(n/2))的复杂性。

如果你想对32到64个元素之间的集合使用此方法，你应该将表示step函数中当前子集的int更改为long，尽管随着集合大小的增加，性能显然会急剧下降。如果你想对一个有奇数个元素的集合使用这个，你应该给这个集合加上一个0，使它成为偶数。

import java.util.ArrayList;
import java.util.List;


public class SubsetSumMiddleAttack {
static final int target = 100000000;
static final int[] set = new int[]{ ... };


static List<Subset> evens = new ArrayList<>();
static List<Subset> odds = new ArrayList<>();


static int[][] split(int[] superSet) {
int[][] ret = new int[2][superSet.length / 2];


for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];


return ret;
}


static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
accumulator.add(new Subset(subset, sum));
if (counter != superSet.length) {
step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
step(superSet, accumulator, subset, sum, counter + 1);
}
}


static void printSubset(Subset e, Subset o) {
String ret = "";
for (int i = 0; i < 32; i++) {
if (i % 2 == 0) {
if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
else {
if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
}
if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
System.out.println(ret);
}


public static void main(String[] args) {
int[][] superSets = split(set);


step(superSets[0], evens, 0,0,0);
step(superSets[1], odds, 0,0,0);


for (Subset e : evens) {
for (Subset o : odds) {
if (e.sum + o.sum == target) printSubset(e, o);
}
}
}
}


class Subset {
int subset;
int sum;


Subset(int subset, int sum) {
this.subset = subset;
this.sum = sum;
}
}

小开

Java解决方案的Swift 3转换(by @JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}




extension Array where Element: _IntType {


func subsets(to: Int) -> [[Element]]? {


func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {


var sum: Int = 0
for x in partial {
sum += x as! Int
}


if sum == target {
solution.append(partial)
}


guard sum < target else {
return
}


for i in stride(from: 0, to: numbers.count, by: 1) {


var remaining = [Element]()


for j in stride(from: i + 1, to: numbers.count, by: 1) {
remaining.append(numbers[j])
}


var partial_rec = [Element](partial)
partial_rec.append(numbers[i])


sum_up_recursive(remaining, target, partial_rec, &solution)
}
}


var solutions = [[Element]]()
sum_up_recursive(self, to, [Element](), &solutions)


return solutions.count > 0 ? solutions : nil
}


}

用法:

let numbers = [3, 9, 8, 4, 5, 7, 10]


if let solution = numbers.subsets(to: 15) {
print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
print("not possible")
}

小开

我在做类似的scala作业。我想在这里发布我的解决方案:

 def countChange(money: Int, coins: List[Int]): Int = {
def getCount(money: Int, remainingCoins: List[Int]): Int = {
if(money == 0 ) 1
else if(money < 0 || remainingCoins.isEmpty) 0
else
getCount(money, remainingCoins.tail) +
getCount(money - remainingCoins.head, remainingCoins)
}
if(money == 0 || coins.isEmpty) 0
else getCount(money, coins)
}

小开

下面是一个更好的版本，具有更好的输出格式和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);
}
}

小开

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

小开

这是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))
}
}

小开

建议回答:

下面是一个使用es2015 发电机的解决方案:

function* subsetSum(numbers, target, partial = [], partialSum = 0) {


if(partialSum === target) yield partial


if(partialSum >= target) return


for(let i = 0; i < numbers.length; i++){
const remaining = numbers.slice(i + 1)
, n = numbers[i]


yield* subsetSum(remaining, target, [...partial, n], partialSum + n)
}


}

使用生成器实际上非常有用，因为它允许您在找到有效子集时立即暂停脚本执行。这与没有生成器(即缺乏状态)的解决方案形成对比，后者必须遍历numbers的每个子集

小开

Java非递归版本，简单地不断添加元素并在可能的值之间重新分配它们。0将被忽略，适用于固定列表(给定的是您可以使用的内容)或可重复数字列表。

import java.util.*;


public class TestCombinations {


public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() \{\{
add(4);
add(10);
add(25);
}};


System.out.println("## each element can appear as many times as needed");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, true);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}


System.out.println("## each element can appear only once");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, false);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}
}


public static class Combinations {
private boolean allowRepetitions;
private int[] repetitions;
private ArrayList<Integer> numbers;
private Integer target;
private Integer sum;
private boolean hasNext;
private Set<String> combinations;


/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target  Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target) {
this(numbers, target, true);
}


/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target  Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
this.allowRepetitions = allowRepetitions;
if (this.allowRepetitions) {
Set<Integer> numbersSet = new HashSet<>(numbers);
this.numbers = new ArrayList<>(numbersSet);
} else {
this.numbers = numbers;
}
this.numbers.removeAll(Arrays.asList(0));
Collections.sort(this.numbers);


this.target = target;
this.repetitions = new int[this.numbers.size()];
this.combinations = new LinkedHashSet<>();


this.sum = 0;
if (this.repetitions.length > 0)
this.hasNext = true;
else
this.hasNext = false;
}


/**
* Calculate and return the sum of the current combination.
*
* @return The sum.
*/
private Integer calculateSum() {
this.sum = 0;
for (int i = 0; i < repetitions.length; ++i) {
this.sum += repetitions[i] * numbers.get(i);
}
return this.sum;
}


/**
* Redistribute picks when only one of each number is allowed in the sum.
*/
private void redistribute() {
for (int i = 1; i < this.repetitions.length; ++i) {
if (this.repetitions[i - 1] > 1) {
this.repetitions[i - 1] = 0;
this.repetitions[i] += 1;
}
}
if (this.repetitions[this.repetitions.length - 1] > 1)
this.repetitions[this.repetitions.length - 1] = 0;
}


/**
* Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
*
* @return The sum.
*/
private Integer next() {
if (this.hasNext && this.repetitions.length > 0) {
this.repetitions[0] += 1;
if (!this.allowRepetitions)
this.redistribute();
this.calculateSum();


for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
if (this.sum > this.target) {
this.repetitions[i] = 0;
if (i + 1 < this.repetitions.length) {
this.repetitions[i + 1] += 1;
if (!this.allowRepetitions)
this.redistribute();
}
this.calculateSum();
}
}


if (this.sum.compareTo(0) == 0)
this.hasNext = false;
}
return this.sum;
}


/**
* Calculate all combinations whose sum equals target.
*/
public void calculateCombinations() {
while (this.hasNext) {
if (this.next().compareTo(target) == 0)
this.combinations.add(this.toString());
}
}


/**
* Return all combinations whose sum equals target.
*
* @return Combinations as a set of strings.
*/
public Set<String> getCombinations() {
return this.combinations;
}


@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
for (int i = 0; i < repetitions.length; ++i) {
for (int j = 0; j < repetitions[i]; ++j) {
stringBuilder.append(numbers.get(i) + " ");
}
}
return stringBuilder.toString();
}
}
}

样例输入:

numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25

样例输出:

## each element can appear as many times as needed
4: 1 1 1 1
4: 1 1 2
4: 2 2
10: 1 1 1 1 1 1 1 1 1 1
10: 1 1 1 1 1 1 1 1 2
10: 1 1 1 1 1 1 2 2
10: 1 1 1 1 2 2 2
10: 1 1 2 2 2 2
10: 2 2 2 2 2
10: 1 1 1 1 1 5
10: 1 1 1 2 5
10: 1 2 2 5
10: 5 5
10: 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2
25: 1 2 2 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5
25: 1 1 1 1 2 2 2 2 2 2 2 2 5
25: 1 1 2 2 2 2 2 2 2 2 2 5
25: 2 2 2 2 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5
25: 1 1 1 1 1 1 1 2 2 2 2 5 5
25: 1 1 1 1 1 2 2 2 2 2 5 5
25: 1 1 1 2 2 2 2 2 2 5 5
25: 1 2 2 2 2 2 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 5 5 5
25: 1 1 1 1 1 1 1 1 2 5 5 5
25: 1 1 1 1 1 1 2 2 5 5 5
25: 1 1 1 1 2 2 2 5 5 5
25: 1 1 2 2 2 2 5 5 5
25: 2 2 2 2 2 5 5 5
25: 1 1 1 1 1 5 5 5 5
25: 1 1 1 2 5 5 5 5
25: 1 2 2 5 5 5 5
25: 5 5 5 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10
25: 1 1 1 1 1 1 1 1 1 2 2 2 10
25: 1 1 1 1 1 1 1 2 2 2 2 10
25: 1 1 1 1 1 2 2 2 2 2 10
25: 1 1 1 2 2 2 2 2 2 10
25: 1 2 2 2 2 2 2 2 10
25: 1 1 1 1 1 1 1 1 1 1 5 10
25: 1 1 1 1 1 1 1 1 2 5 10
25: 1 1 1 1 1 1 2 2 5 10
25: 1 1 1 1 2 2 2 5 10
25: 1 1 2 2 2 2 5 10
25: 2 2 2 2 2 5 10
25: 1 1 1 1 1 5 5 10
25: 1 1 1 2 5 5 10
25: 1 2 2 5 5 10
25: 5 5 5 10
25: 1 1 1 1 1 10 10
25: 1 1 1 2 10 10
25: 1 2 2 10 10
25: 5 10 10
25: 1 1 1 1 1 20
25: 1 1 1 2 20
25: 1 2 2 20
25: 5 20
## each element can appear only once
4: 2 2
10: 1 2 2 5
10: 10
25: 1 2 2 20
25: 5 20

小开

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

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

function items2T([n,...ns],t){
var c = ~~(t/n);
return ns.length ? Array(c+1).fill()
.reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
: t % n ? []
: [Array(c).fill(n)];
};


var data = [3, 9, 8, 4, 5, 7, 10],
result;


console.time("combos");
result = items2T(data, 15);
console.timeEnd("combos");
console.log(JSON.stringify(result));

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

小开

Perl版本(前导答案):

use strict;


sub subset_sum {
my ($numbers, $target, $result, $sum) = @_;


print 'sum('.join(',', @$result).") = $target\n" if $sum == $target;
return if $sum >= $target;


subset_sum([@$numbers[$_ + 1 .. $#$numbers]], $target,
[@{$result||[]}, $numbers->[$_]], $sum + $numbers->[$_])
for (0 .. $#$numbers);
}


subset_sum([3,9,8,4,5,7,10,6], 15);

结果:

sum(3,8,4) = 15
sum(3,5,7) = 15
sum(9,6) = 15
sum(8,7) = 15
sum(4,5,6) = 15
sum(5,10) = 15

Javascript版本:

const subsetSum = (numbers, target, partial = [], sum = 0) => {
if (sum < target)
numbers.forEach((num, i) =>
subsetSum(numbers.slice(i + 1), target, partial.concat([num]), sum + num));
else if (sum == target)
console.log('sum(%s) = %s', partial.join(), target);
}


subsetSum([3,9,8,4,5,7,10,6], 15);

Javascript一行实际返回结果(而不是打印它):

const subsetSum=(n,t,p=[],s=0,r=[])=>(s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,[...p,l],s+l,r)):s==t?r.push(p):0,r);


console.log(subsetSum([3,9,8,4,5,7,10,6], 15));

我最喜欢的是带有回调的一行语句:

const subsetSum=(n,t,cb,p=[],s=0)=>s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,cb,[...p,l],s+l)):s==t?cb(p):0;


subsetSum([3,9,8,4,5,7,10,6], 15, console.log);

小开

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

小开

import java.util.*;


public class Main{


int recursionDepth = 0;
private int[][] memo;


public static void main(String []args){
int[] nums = new int[] {5,2,4,3,1};
int N = nums.length;
Main main =  new Main();
main.memo = new int[N+1][N+1];
main._findCombo(0, N-1,nums, 8, 0, new LinkedList() );
System.out.println(main.recursionDepth);
}




private void _findCombo(
int from,
int to,
int[] nums,
int targetSum,
int currentSum,
LinkedList<Integer> list){


if(memo[from][to] != 0) {
currentSum = currentSum + memo[from][to];
}


if(currentSum > targetSum) {
return;
}


if(currentSum ==  targetSum) {
System.out.println("Found - " +list);
return;
}


recursionDepth++;


for(int i= from ; i <= to; i++){
list.add(nums[i]);
memo[from][i] = currentSum + nums[i];
_findCombo(i+1, to,nums, targetSum, memo[from][i], list);
list.removeLast();
}


}
}

小开

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

小开

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

下面是一个O(size_of_array * (number_of_sums + 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，我们已经意识到我们的目标是正的，所以sign = 1。我们已经对输入进行了排序，因此array = [-11, -7, -5, -3, -2, 2, 3, 5, 7, 11]. c。由于我们经常通过索引访问它，下面是从索引到值的映射:

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) * sign阻止我们记录超过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。这是我们打印出来的第一个解。

现在我们来到recur子函数。因为它是在main函数内部定义的，所以它可以看到last_index。

首先要注意的是，它调用yield，而不是return。这使它成为发电机。当你调用它时，返回一个特殊类型的迭代器。当你循环遍历那个迭代器时，你会得到一个它能产生的所有东西的列表。但你是在生成它们时得到它们的。如果它是一个很长的列表，你不把它放在内存中。(有点重要，因为我们可以得到一个很长的列表。)

recur(new_target, max_i)将产生的是你可以只使用array的元素和最大索引max_i来总结为new_target的所有方式。这就是它的答案:“我们必须在索引max_i+1之前到达new_target。”当然，它是递归的。

因此，recur(target, len(array))是所有使用任何索引达到目标的解决方案。这就是我们想要的。

小开

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++堆栈解决方案。与其他迭代解决方案不同的是，它不会对中间序列进行不必要的复制。

#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):