我有以下的代码。我需要找到该数组中所有数字之和为目标值100000的组合。问题在于下面的解决方案并不包括这样一对数字
所以最终的任务是找到所有数字之和为目标值的组合,每个组合只应包含3个数字,并且
有什么想法如何解决这个问题吗?
20000 40000 40000
。这是因为在每次递归时,我都会取出一个数字(请看 filter
功能)。如果我没有使用filter
,那么就会发生最大调用栈溢出。所以最终的任务是找到所有数字之和为目标值的组合,每个组合只应包含3个数字,并且
0
也要参与。有什么想法如何解决这个问题吗?
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 && partial.length === 3) {
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.filter(num => num != n);
subsetSum(remaining, target, partial.concat([n]));
}
}
subsetSum([0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000], 100000);
partial.length === 3
- Nika Kurashvili