我需要数出所有可能的数字组合才能达到给定的总和。
它们应该是非递减的(下一个数字应该大于或等于前一个)。
以下是JavaScript代码和解决问题的示例,但它对以下数字有效期很长
200
:
function spreadInteger(N) {
function generateCombinations(current, remaining, start) {
if (remaining === 0) {
console.log(current.join(" ")); // here I can just put counter and remove `current` variable from arguments to make it faster but it is will be still not enough
return;
}
for (let i = start; i <= remaining; i++) {
generateCombinations([...current, i], remaining - i, i);
}
}
generateCombinations([], N, 1);
}
// spreadInteger(1); // 1 combination
// 1
// spreadInteger(2); // 2 combinations
// 1 1
// 2
// spreadInteger(3); // 3 combinations
// 1 1 1
// 1 2
// 3
// spreadInteger(4); // 5 combinations
// 1 1 1 1
// 1 1 2
// 1 3
// 2 2
// 4
// spreadInteger(5); // 7 combinations
// 1 1 1 1 1
// 1 1 1 2
// 1 1 3
// 1 2 2
// 1 4
// 2 3
// 5
我怎样才能数得更快?
我不需要记录所有的组合,我只需要计算给定数字N有多少这样的组合。
我不关心用编程语言来解决它。我只关心解决方案,所以即使是伪代码的答案也会被接受。
如果可以加快计算速度,也可以假设没有内存限制。