所有可能的不同非递减数字序列（组合），以快速达到给定的总和

Question

我需要计算所有可能的数字组合以达到给定的总和。 它们应该是非递减的（每个下一个数字应该大于或等于前一个数字）。 这是 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 有多少个这样的组合。 我不关心解决它的编程语言。我只关心解决方案，所以即使是伪代码答案也会被接受。 如果可以加快计算速度，还假设没有内存限制。

Answer 1

您想要计算整数 n 的

分区

。这样做的数学函数是分配函数，它在维基页面上列出了一个很好的递归关系：

p(n) = sum((-1^k) * p(n - k*(3*k-1)/2)

每一项中从

n

减去的值是五边形数，它们本身有一个很好的封闭式表达式：

(3*n^2 - n) / 2

这意味着您可以通过从

n

逐步构建

O(n^1.5)

值表，在

p(x)

时间内计算整数

1..n

的分区数。