你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
这个问题可以通过所有可能的和的递归组合来解决,过滤掉那些达到目标的和。下面是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
这种类型的算法在接下来的斯坦福大学抽象编程课程中有很好的解释-这个视频非常推荐来理解递归是如何产生解决方案的排列的。
Edit
上面作为一个生成器函数,使它更有用一点。需要Python 3.3+,因为yield来自。
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有点生疏,但我认为很容易理解。
Java解决方案的c#转换(by @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解决方案:(by @emaillenin)
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和目标都是很大的数字,那么就应该得到近似的解。
其他回答
这是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))
}
}
这个问题的一个迭代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
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>());
}
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
这也可以用来打印所有的答案
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的阶