你如何从给定的N个数字中测试所有可能的加法组合，使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0，…} 期望结果:12345
当前回答
我想我应该用这个问题的答案，但我不能，所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解，应该更能取悦纯粹主义者。
我的答案是用Scala(如果我的Scala很烂，我很抱歉，我刚刚开始学习)。findsumcombination的疯狂之处在于对递归的原始列表进行排序和惟一，以防止欺骗。
def findSumCombinations(target: Int, numbers: List[Int]): Int = {
cc(target, numbers.distinct.sortWith(_ < _), List())
}
def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
if (target == 0) {println(solution); 1 }
else if (target < 0 || numbers.length == 0) 0
else
cc(target, numbers.tail, solution)
+ cc(target - numbers.head, numbers, numbers.head :: solution)
}
使用它:
> findSumCombinations(12345, List(1,5,22,15,0,..))
* Prints a whole heap of lists that will sum to the target *
其他回答
我不喜欢上面看到的Javascript解决方案。下面是我使用部分应用、闭包和递归构建的一个:
好的，我主要关心的是，如果组合数组能满足目标要求，希望这样你就能找到剩下的组合了
这里只需要设置目标并传递组合数组。
function main() {
const target = 10
const getPermutationThatSumT = setTarget(target)
const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])
console.log( permutation );
}
我提出的当前实现
function setTarget(target) {
let partial = [];
return function permute(input) {
let i, removed;
for (i = 0; i < input.length; i++) {
removed = input.splice(i, 1)[0];
partial.push(removed);
const sum = partial.reduce((a, b) => a + b)
if (sum === target) return partial.slice()
if (sum < target) permute(input)
input.splice(i, 0, removed);
partial.pop();
}
return null
};
}
这个问题的解决方案在互联网上已经出现过无数次了。这个问题叫做硬币兑换问题。你可以在http://rosettacode.org/wiki/Count_the_coins上找到答案，在http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf上找到数学模型(或谷歌硬币变化问题)。
顺便说一下，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)
sumcombination()函数可以单独使用，并且可以进一步分析结果以显示“最佳”解决方案(最短的列表)或解决方案的数量(列表的数量)。
请注意，即使这样，需求也可能无法完全满足。解决方案中每个列表的顺序可能是重要的。在这种情况下，每个列表都必须重复它的元素组合的次数。或者我们只对不同的组合感兴趣。
例如，我们可以考虑List(5,10)应该给出两种组合:List(5,10)和List(10,5)。对于List(5,5,5)，它可以给出三种组合，也可以只给出一种组合，这取决于需求。对于整数，这三种排列是等价的，但如果我们处理的是硬币，就像在“硬币更换问题”中一样，它们就不一样了。
Also not stated in the requirements is the question of whether each number (or coin) may be used only once or many times. We could (and we should!) generalize the problem to a list of lists of occurrences of each number. This translates in real life into "what are the possible ways to make an certain amount of money with a set of coins (and not a set of coin values)". The original problem is just a particular case of this one, where we have as many occurrences of each coin as needed to make the total amount with each single coin value.
下面是一个Java版本，它非常适合小N和非常大的目标和，当复杂度O(t*N)(动态解)大于指数算法时。我的版本在中间攻击中使用了一个meet，并进行了一些调整，以降低复杂度，从经典的naive O(n*2^n)降低到O(2^(n/2))。
如果你想在32到64个元素之间的集合中使用这种方法，你应该将表示step函数中当前子集的int改为long，尽管随着集合大小的增加，性能显然会急剧下降。如果你想对一个有奇数个元素的集合使用这个，你应该给这个集合加上一个0，使它成为偶数。
import java.util.ArrayList;
import java.util.List;
public class SubsetSumMiddleAttack {
static final int target = 100000000;
static final int[] set = new int[]{ ... };
static List<Subset> evens = new ArrayList<>();
static List<Subset> odds = new ArrayList<>();
static int[][] split(int[] superSet) {
int[][] ret = new int[2][superSet.length / 2];
for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];
return ret;
}
static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
accumulator.add(new Subset(subset, sum));
if (counter != superSet.length) {
step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
step(superSet, accumulator, subset, sum, counter + 1);
}
}
static void printSubset(Subset e, Subset o) {
String ret = "";
for (int i = 0; i < 32; i++) {
if (i % 2 == 0) {
if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
else {
if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
}
}
if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
System.out.println(ret);
}
public static void main(String[] args) {
int[][] superSets = split(set);
step(superSets[0], evens, 0,0,0);
step(superSets[1], odds, 0,0,0);
for (Subset e : evens) {
for (Subset o : odds) {
if (e.sum + o.sum == target) printSubset(e, o);
}
}
}
}
class Subset {
int subset;
int sum;
Subset(int subset, int sum) {
this.subset = subset;
this.sum = sum;
}
}
PHP版本，灵感来自Keith Beller的c#版本。
bala的PHP版本不适合我，因为我不需要对数字进行分组。我想要一个更简单的实现，只有一个目标值和一个数字池。这个函数也会删除任何重复的条目。
编辑25/10/2021:添加精度参数以支持浮点数(现在需要bcmath扩展)。
/**
* Calculates a subset sum: finds out which combinations of numbers
* from the numbers array can be added together to come to the target
* number.
*
* Returns an indexed array with arrays of number combinations.
*
* Example:
*
* <pre>
* $matches = subset_sum(array(5,10,7,3,20), 25);
* </pre>
*
* Returns:
*
* <pre>
* Array
* (
* [0] => Array
* (
* [0] => 3
* [1] => 5
* [2] => 7
* [3] => 10
* )
* [1] => Array
* (
* [0] => 5
* [1] => 20
* )
* )
* </pre>
*
* @param number[] $numbers
* @param number $target
* @param array $part
* @param int $precision
* @return array[number[]]
*/
function subset_sum($numbers, $target, $precision=0, $part=null)
{
// we assume that an empty $part variable means this
// is the top level call.
$toplevel = false;
if($part === null) {
$toplevel = true;
$part = array();
}
$s = 0;
foreach($part as $x)
{
$s = $s + $x;
}
// we have found a match!
if(bccomp((string) $s, (string) $target, $precision) === 0)
{
sort($part); // ensure the numbers are always sorted
return array(implode('|', $part));
}
// gone too far, break off
if($s >= $target)
{
return null;
}
$matches = array();
$totalNumbers = count($numbers);
for($i=0; $i < $totalNumbers; $i++)
{
$remaining = array();
$n = $numbers[$i];
for($j = $i+1; $j < $totalNumbers; $j++)
{
$remaining[] = $numbers[$j];
}
$part_rec = $part;
$part_rec[] = $n;
$result = subset_sum($remaining, $target, $precision, $part_rec);
if($result)
{
$matches = array_merge($matches, $result);
}
}
if(!$toplevel)
{
return $matches;
}
// this is the top level function call: we have to
// prepare the final result value by stripping any
// duplicate results.
$matches = array_unique($matches);
$result = array();
foreach($matches as $entry)
{
$result[] = explode('|', $entry);
}
return $result;
}
例子:
$result = subset_sum(array(5, 10, 7, 3, 20), 25);
这将返回一个包含两个数字组合数组的索引数组:
3, 5, 7, 10
5, 20
浮点数示例:
// Specify the precision in the third argument
$result = subset_sum(array(0.40, 0.03, 0.05), 0.45, 2);
这将返回一个匹配项:
0.40, 0.05
这个问题可以通过所有可能的和的递归组合来解决，过滤掉那些达到目标的和。下面是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和目标都是很大的数字，那么就应该得到近似的解。
