你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
首先推导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()是无关紧要的,因为算法最终会减少递归调用。
其他回答
我想我应该用这个问题的答案,但我不能,所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解,应该更能取悦纯粹主义者。
我的答案是用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 *
func sum(array : [Int]) -> Int{
var sum = 0
array.forEach { (item) in
sum = item + sum
}
return sum
}
func susetNumbers(array :[Int], target : Int, subsetArray: [Int],result : inout [[Int]]) -> [[Int]]{
let s = sum(array: subsetArray)
if(s == target){
print("sum\(subsetArray) = \(target)")
result.append(subsetArray)
}
for i in 0..<array.count{
let n = array[i]
let remaning = Array(array[(i+1)..<array.count])
susetNumbers(array: remaning, target: target, subsetArray: subsetArray + [n], result: &result)
}
return result
}
var resultArray = [[Int]]()
let newA = susetNumbers(array: [1,2,3,4,5], target: 5, subsetArray: [],result:&resultArray)
print(resultArray)
这个问题的一个迭代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
另一个python解决方案是使用itertools.combination模块,如下所示:
#!/usr/local/bin/python
from itertools import combinations
def find_sum_in_list(numbers, target):
results = []
for x in range(len(numbers)):
results.extend(
[
combo for combo in combinations(numbers ,x)
if sum(combo) == target
]
)
print results
if __name__ == "__main__":
find_sum_in_list([3,9,8,4,5,7,10], 15)
输出:[(8,7),(5,10),(3,8,4),(3,5,7)]
下面是一个更好的版本,具有更好的输出格式和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);
}
}