你如何从给定的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和目标都是很大的数字，那么就应该得到近似的解。
其他回答
首先推导0。0是加法的一个恒等式所以在这个特殊情况下，它在单类定律下是没有用的。如果你想向上爬到一个正数，也可以推导出负数。否则还需要做减法运算。
所以…在这个特定的作业中，你能得到的最快算法如下所示。
函数items2T ([n,……ns), t) { Var c = ~~(t/n); 返回ns。长度呢?数组(c + 1) .fill () .reduce((r，_，i) => r.concat(items2T(ns, t-n*i)。map(s => Array(i).fill(n).concat(s)))，[]) : t % n ?［］ :[数组(c) .fill (n)); }; Var数据= [3,9,8,4,5,7,10]， 结果; console.time(“组合”); result = items2T(data, 15); console.timeEnd(“组合”); console.log (JSON.stringify(结果));
这是一个非常快的算法，但如果你对数据数组进行降序排序，它会更快。使用.sort()是无关紧要的，因为算法最终会减少递归调用。
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
这是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))
}
}
这个问题可以通过所有可能的和的递归组合来解决，过滤掉那些达到目标的和。下面是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和目标都是很大的数字，那么就应该得到近似的解。
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>());
}
推荐文章
- 设计模式:工厂vs工厂方法vs抽象工厂
- 如何计算圆周长上的一点?
- 为什么处理排序数组比未排序数组慢?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下，您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 构造函数何时抛出异常是正确的?
- 什么是“一级”对象?
- 什么时候应该使用Debug.Assert()?
- 为什么浮点数不准确?
- 如何找到最近修改文件的git提交?
- 如何使用JavaScript比较软件版本号?数量(只)
- IOException:进程不能访问文件“文件路径”，因为它正在被另一个进程使用
- 地图和字典的区别是什么?
- 如何使Vim不突出显示所搜索的内容?
