你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
function solve(n){
let DP = [];
DP[0] = DP[1] = DP[2] = 1;
DP[3] = 2;
for (let i = 4; i <= n; i++) {
DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
}
return DP[n]
}
console.log(solve(5))
这是JS的一个动态解决方案,告诉任何人有多少种方法可以得到一定的总和。如果考虑到时间和空间的复杂性,这可能是正确的解决方案。
其他回答
这也可以用来打印所有的答案
public void recur(int[] a, int n, int sum, int[] ans, int ind) {
if (n < 0 && sum != 0)
return;
if (n < 0 && sum == 0) {
print(ans, ind);
return;
}
if (sum >= a[n]) {
ans[ind] = a[n];
recur(a, n - 1, sum - a[n], ans, ind + 1);
}
recur(a, n - 1, sum, ans, ind);
}
public void print(int[] a, int n) {
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
时间复杂度是指数级的。2^n的阶
这个问题的一个迭代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
我想我应该用这个问题的答案,但我不能,所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解,应该更能取悦纯粹主义者。
我的答案是用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 *
在Haskell:
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]
J:
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...
正如您可能注意到的,两者都采用相同的方法,并将问题分为两部分:生成幂集的每个成员,并检查每个成员与目标的和。
还有其他的解决方案,但这是最直接的。
在这两种方法中,你是否需要帮助,或者找到另一种方法?
@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);
}
}'