你如何从给定的N个数字中测试所有可能的加法组合，使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0，…} 期望结果:12345
当前回答
这类似于硬币更换问题
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;
}
}
其他回答
这类似于硬币更换问题
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;
}
}
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
到目前为止，有很多解决方案，但都是生成然后过滤的形式。这意味着他们可能会在递归路径上花费大量时间，而这些递归路径不会导致解决方案。
这里的解决方案是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))是所有使用任意索引到达目标的解。这就是我们想要的。
非常有效的算法，使用我几年前用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");
}
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")
}
推荐文章
- 设计模式:工厂vs工厂方法vs抽象工厂
- 如何计算圆周长上的一点?
- 为什么处理排序数组比未排序数组慢?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下，您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 构造函数何时抛出异常是正确的?
- 什么是“一级”对象?
- 什么时候应该使用Debug.Assert()?
- 为什么浮点数不准确?
- 如何找到最近修改文件的git提交?
- 如何使用JavaScript比较软件版本号?数量(只)
- IOException:进程不能访问文件“文件路径”，因为它正在被另一个进程使用
- 地图和字典的区别是什么?
- 如何使Vim不突出显示所搜索的内容?
