algorithm - 不同的 n 个数字，使总和等于 N

Question

假设我想在从 1 到 N 的范围内找到 n 个不同的数字，以便它们的总和等于 N。例如

n = 3, N = 10: the numbers will be (2, 3, 5);
n = 4, N = 10: the numbers will be (1, 2, 3, 4).

虽然找出该问题的所有可能组合将花费指数时间，但我正在寻找“最小”组合，即最大的数字是最小的。例如，

在 n = 4 和 N = 12 的情况下，(6, 3, 2, 1) 和 (5, 4, 2, 1)可能是解决方案，但我只对 (5, 4, 2, 1) 感兴趣。

对于这个问题，会不会有时间复杂度更好的算法？我听说过对数合并，但不确定如何在此处应用它。

如果需要说明问题的任何详细信息，请告诉我。始终如一，我们将不胜感激。

Answer 1

这个问题有一个简单的贪心算法。

首先，有n个元素按升序排列，为了使它们不同，每个元素应该至少比它的前一个元素大一个。

所以，我们有

1, 2, 3 ... , n

现在，所有 n 的总和号码是n*(n + 1)/2

剩下的就是left = N - n*(n + 1)/2

为了让最后一个元素尽可能小，我们需要将left分散开来所有数字的差异

所以，我们有

1 + left/n, 2 + left/n, ..., n + left/n

如果left % n != 0 ，我们只需要在最后一个 left % n 上加 1元素。

注意:如果N < n*(n + 1)/2 , 无解

例子:

所以，对于 n = 4 和 N = 12

First, we start with

1, 2, 3, 4

left = 12 - (4*5/2) = 2

So, now we have

1 + (2/4), 2 + (2/4), 3 + (2/4), 4 + (2/4) = 1, 2, 3, 4

As left % n = 2
Finally, we have

1, 2, 3 + 1, 4 + 1 = 1, 2, 4, 5

类似地，对于 n = 3，N = 10

First, we start with

1, 2, 3

left = 10 - (3*4/2) = 4

So, now we have

1 + (4/3), 2 + (4/3), 3 + (4/3) = 2, 3, 4

As left % n = 1
Finally, we have

2, 3, 4 + 1 = 2, 3, 5

伪代码，时间复杂度O(n)

int[]result = new int[n];
int left = N - n*(n + 1)/2;

for(int i = 0; i < n; i++){
    result[i] = i + 1 + left/n;
    if(i >= n - (left % n)){//Add extra one for last left % n elements
        result[i]++;
    }
}
return result;