你如何从给定的N个数字中测试所有可能的加法组合，使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0，…} 期望结果:12345
当前回答
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")
}
其他回答
用excel找到组合(相当容易)。 (你的电脑不能太慢)
去这个网站 进入“Sum to Target”页面 下载“Sum to Target”excel文件。 按照网站页面上的说明操作。
希望这能有所帮助。
到目前为止，有很多解决方案，但都是生成然后过滤的形式。这意味着他们可能会在递归路径上花费大量时间，而这些递归路径不会导致解决方案。
这里的解决方案是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))是所有使用任意索引到达目标的解。这就是我们想要的。
下面是一个Java版本，它非常适合小N和非常大的目标和，当复杂度O(t*N)(动态解)大于指数算法时。我的版本在中间攻击中使用了一个meet，并进行了一些调整，以降低复杂度，从经典的naive 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;
}
}
这个问题的解决方案在互联网上已经出现过无数次了。这个问题叫做硬币兑换问题。你可以在http://rosettacode.org/wiki/Count_the_coins上找到答案，在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf上找到数学模型(或谷歌硬币变化问题)。
顺便说一下，Tsagadai的Scala解决方案很有趣。本例生成1或0。作为一个副作用，它在控制台上列出了所有可能的解决方案。它显示解决方案，但无法以任何方式使其可用。
为了尽可能有用，代码应该返回一个List[List[Int]]，以允许获得解决方案的数量(列表列表的长度)，“最佳”解决方案(最短的列表)，或所有可能的解决方案。
这里有一个例子。它效率很低，但很容易理解。
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)
sumcombination()函数可以单独使用，并且可以进一步分析结果以显示“最佳”解决方案(最短的列表)或解决方案的数量(列表的数量)。
请注意，即使这样，需求也可能无法完全满足。解决方案中每个列表的顺序可能是重要的。在这种情况下，每个列表都必须重复它的元素组合的次数。或者我们只对不同的组合感兴趣。
例如，我们可以考虑List(5,10)应该给出两种组合:List(5,10)和List(10,5)。对于List(5,5,5)，它可以给出三种组合，也可以只给出一种组合，这取决于需求。对于整数，这三种排列是等价的，但如果我们处理的是硬币，就像在“硬币更换问题”中一样，它们就不一样了。
Also not stated in the requirements is the question of whether each number (or coin) may be used only once or many times. We could (and we should!) generalize the problem to a list of lists of occurrences of each number. This translates in real life into "what are the possible ways to make an certain amount of money with a set of coins (and not a set of coin values)". The original problem is just a particular case of this one, where we have as many occurrences of each coin as needed to make the total amount with each single coin value.
非常有效的算法，使用我几年前用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");
}
