查找所有可能的数字组合以达到给定的总和
你将如何去测试给定数字集合中所有可能的加法组合，以便它们加起来给定最终数字？
例：
这个问题可以通过递归组合所有可能的总和来解决，这些总和可以过滤那些到达目标的总和。 这里是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
在下面的斯坦福大学抽象编程讲座中很好地解释了这种类型的算法 - 该视频非常值得推荐，以了解递归如何生成解决方案的排列。
编辑
以上作为生成器函数，使其更有用。 需要Python 3.3+，因为yield from 。
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＃转换:(由@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解决方案:(通过@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和Target是大数字，则应该转换为解决方案的近似版本。
在Haskell中：
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
和J：
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...
您可能会注意到，两者都采用相同的方法，并将问题分为两部分：生成权力集的每个成员，并检查每个成员的总和。
还有其他的解决方案，但这是最直接的。
你需要任何一方的帮助，还是寻找不同的方法？
这个问题的解决方案已经在互联网上获得了一百万次。 这个问题被称为硬币改变问题。 人们可以在http://rosqtacode.org/wiki/Count_the_coins找到解决方案，并在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf（或Google硬币更换问题）。
顺便说一句，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)
sumCombinations()函数本身可以使用，并且可以进一步分析结果以显示“最佳”解决方案（最短列表）或解决方案数目（列表数量）。
请注意，即使如此，这些要求可能不完全满足。 可能发生的问题是解决方案中每个列表的顺序都很重要。 在这种情况下，每个列表都必须重复尽可能多的时间，因为它们的元素组合在一起。 或者我们可能只对不同的组合感兴趣。
例如，我们可以考虑List(5, 10)应该给出两种组合： List(5, 10)和List(10, 5) 。 对于List(5, 5, 5)它可以给出三种组合或一种，这取决于要求。 对于整数，这三种排列是等价的，但如果我们正在处理硬币，就像在“硬币改变问题”中那样，它们不是。
在要求中也没有规定每个数字（或硬币）是否只能使用一次或多次的问题。 我们可以（也应该！）将问题概括为每个数字出现次数列表。 这在现实生活中转化为“用一组硬币（而不是一组硬币值）来赚取一定数量的金钱的可能方式”。 原来的问题仅仅是这个问题的一个特例，在这个问题中，每个硬币的出现次数与每个硬币的总金额一样多。
链接地址: http://www.djcxy.com/p/64419.html上一篇: Finding all possible combinations of numbers to reach a given sum