假设我想在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)感兴趣。
对于这个问题，是否有更好时间复杂度的算法？我听说过对数合并，但不确定如何在此应用。
如果需要指定问题的任何细节，请告诉我。再次感谢您的帮助。
对于这个问题，有一个简单的贪心算法。
首先，有 n 个按升序排列的元素，为了使它们不同，每个元素应该比其前面的元素至少大1。
因此，我们有
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，我们只需要将额外的1添加到最后的 left % n 个元素中。
注意: 如果 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;
假设你有一个函数 f(n, N, sum) - 它将返回一个结果，该结果将显示你从范围 1 到 N 中取 n 个元素相加得到 sum 的可能性。
至少现在你可以通过简单调用 f(n, N, N) 来确定解是否存在。
假设对于给定的 n、N 和 sum，问题 p(n,N,sum) 有解，并且 x 是结果中最小的最大数。那么问题 p(n',N',sum') 也应该有解，其中 n'=n-1，N'=x-1，sum'=sum-x。问题 p(0,N,0) 总是有解，并且它是归纳的基础。
函数f(n, N, sum)将返回范围在1到N之间的最小数x，该数可以成为解的一部分（否则应返回-1或指示无解的内容）。我们可以尝试将1到N中的每个数字作为x，并检查是否存在f(n - 1, x - 1, sum - x)的解。
关键在于使用记忆化技术，以避免重复计算相同的函数。只需记住找到的x即可。记忆化每个可能的输入组合最多需要O(n * N * N)的空间，并且需要相同的O(n * N * N)时间进行计算。此外，如果sum>N*(N+1)/2，则没有解，我们可以立即剪枝这样的调用。这是多项式时间/空间复杂度，比指数时间/空间复杂度更好。
让我们试着解决这个问题，假设我们在[1, N]之间有n个不同的数字。最小可能的总和是什么？它将是前n个自然数的总和，即
1 + 2 + 3 + 4 + ... + n
可能的最大数字是
(N-n+1) + (N-n+2) + (N-n+3) + ... + (N-n+n)
S = 1 + 2 + ... + n
S = 1 + 2 + ... + n + x*n <= N
这个可以几乎瞬间计算出来。答案通常要么是以 N/n 为中心的一串数字，要么是以基本相同的中心为中心的一串数字，中间有一个间隙。
所以先计算出中间值，然后计算是否需要间隙以及在哪里需要。然后你就完成了。
如果 n 是奇数，则中间值为 N/n（假设为整数除法），右移足够多的位数以考虑余数。例如，如果 N 是10000，n 是17，则中间值为588，起始范围为588 ± (17-1)/2，即580-596。但余数为4，所以向右移动4个单位，答案将是580-592、594-597。
n 是从半数开始的中间数。那么中间数就是 (N-n/2)/n + 0.5。例如，如果 N 是10000，n 是18，那么中间数就是555.5，你的起始范围就是555.5 ± (18-1)/2，即547-564。但是这个除法有余数，所以我们得到的答案是547-563，565。
2, 3, 5。 - Pham Trung