你如何从给定的N个数字中测试所有可能的加法组合，使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0，…} 期望结果:12345
当前回答
到目前为止，有很多解决方案，但都是生成然后过滤的形式。这意味着他们可能会在递归路径上花费大量时间，而这些递归路径不会导致解决方案。
这里的解决方案是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))是所有使用任意索引到达目标的解。这就是我们想要的。
其他回答
到目前为止，有很多解决方案，但都是生成然后过滤的形式。这意味着他们可能会在递归路径上花费大量时间，而这些递归路径不会导致解决方案。
这里的解决方案是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))是所有使用任意索引到达目标的解。这就是我们想要的。
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)
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();
}
?>
这也可以用来打印所有的答案
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的阶
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) 数字。forEach((num, i) => subsetSum(数字。Slice (i + 1)， target, partial.concat([num])， sum + num)); Else if (sum == target) console.log(的总和(% s) = % s, partial.join(),目标); ｝ 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,辛西娅·布雷齐尔,p =黑铝,s = 0) = > s & lt; t ? n.forEach ((l, i) = > subsetSum (n.slice (i + 1)、t、辛西娅·布雷齐尔,黑... p, l铝,s + l)): s = = t ?辛西娅·布雷齐尔(p): 0; 子集（[3,9,8,4,5,7,10,6]，15,console.log）；
