你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
下面是一个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;
}
}
其他回答
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
@KeithBeller的回答略有变化的变量名称和一些评论。
public static void Main(string[] args)
{
List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
int targetSum = 15;
SumUp(input, targetSum);
}
public static void SumUp(List<int> input, int targetSum)
{
SumUpRecursive(input, targetSum, new List<int>());
}
private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
{
// Sum up partial
int sum = 0;
foreach (int x in listToSum)
sum += x;
//Check sum matched
if (sum == targetSum)
Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);
//Check sum passed
if (sum >= targetSum)
return;
//Iterate each input character
for (int i = 0; i < remaining.Count; i++)
{
//Build list of remaining items to iterate
List<int> newRemaining = new List<int>();
for (int j = i + 1; j < remaining.Count; j++)
newRemaining.Add(remaining[j]);
//Update partial list
List<int> newListToSum = new List<int>(listToSum);
int currentItem = remaining[i];
newListToSum.Add(currentItem);
SumUpRecursive(newRemaining, targetSum, newListToSum);
}
}'
下面是一个更好的版本,具有更好的输出格式和c++ 11特性:
void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums)
{
int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
if (currentSum > target)
return;
if (currentSum == target)
{
std::cout << "sum([";
for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
cout << *it << ",";
cout << *std::prev(partialNums.end());
std::cout << "])=" << target << std::endl;
}
for (auto it = nums.begin(); it != nums.end(); ++it)
{
std::vector<int> remaining;
for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
remaining.push_back(*it2);
std::vector<int> partial = partialNums;
partial.push_back(*it);
subset_sum_rec(remaining, target, partial);
}
}
在Haskell:
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
J:
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...
正如您可能注意到的,两者都采用相同的方法,并将问题分为两部分:生成幂集的每个成员,并检查每个成员与目标的和。
还有其他的解决方案,但这是最直接的。
在这两种方法中,你是否需要帮助,或者找到另一种方法?
这类似于硬币更换问题
public class CoinCount
{
public static void main(String[] args)
{
int[] coins={1,4,6,2,3,5};
int count=0;
for (int i=0;i<coins.length;i++)
{
count=count+Count(9,coins,i,0);
}
System.out.println(count);
}
public static int Count(int Sum,int[] coins,int index,int curSum)
{
int count=0;
if (index>=coins.length)
return 0;
int sumNow=curSum+coins[index];
if (sumNow>Sum)
return 0;
if (sumNow==Sum)
return 1;
for (int i= index+1;i<coins.length;i++)
count+=Count(Sum,coins,i,sumNow);
return count;
}
}