求无需内存存储、逐一生成固定长度和为X的有序组合的算法

当然存在这样的算法！你要解决的是固定长度N、元素和为X的有序非负整数组合的迭代生成问题——也就是把X拆分成N个非负整数的有序排列，并且不需要一次性存储所有结果，而是逐个获取下一个组合，这完全可以通过一个轻量的迭代算法实现，内存开销极低。

这个问题本质上等价于「把X个相同的球放入N个有序盒子」的所有放法，你给出的例子顺序是优先把球放在左边盒子，逐步将左边的球转移到右侧的顺序。我们可以基于当前组合，通过局部调整直接推导下一个组合，不需要回溯或预存所有结果。

核心迭代逻辑（NEXT方法） #

假设当前组合是长度为N的数组arr，生成下一个组合的步骤如下：

1. 终止判断：如果当前组合的最后一个元素是X（也就是arr[N-1] = X），说明已经是最后一个组合，没有下一个了。
2. 寻找调整位置：从右往左遍历数组（从倒数第二个元素开始），找到第一个非零元素的位置k（即arr[k] > 0，且k < N-1）。
3. 计算右侧总和：统计k右侧所有元素的和right_sum。
4. 调整组合：
   • 将arr[k]减1；
   • 将arr[k+1]设为right_sum + 1（把k减少的1，加上右侧所有球的总数，放到k的下一个盒子里）；
   • 将k+2到数组末尾的所有元素设为0。
5. 返回调整后的数组，这就是下一个组合。

伪代码示例 #

# 输入：当前组合arr，数组长度N，目标和X
# 输出：下一个组合，若已到末尾则返回null
function nextCombination(arr, N, X):
    # 检查是否为最后一个组合
    if arr[N-1] == X:
        return null
    
    # 从右往左找第一个非零元素的位置k（k < N-1）
    k = N - 2
    while k >= 0 and arr[k] == 0:
        k -= 1
    
    # 计算k右侧元素的总和
    right_sum = 0
    for i in range(k+1, N):
        right_sum += arr[i]
    
    # 调整组合
    arr[k] -= 1
    arr[k+1] = right_sum + 1
    # 清空k+2及以后的元素
    for i in range(k+2, N):
        arr[i] = 0
    
    return arr

例子验证（X=3，N=4） #

我们用你的例子来验证：

• 初始组合：[3, 0, 0, 0]
• 第一次调用NEXT：找到k=0，right_sum=0，调整后得到[2, 1, 0, 0]
• 第二次调用NEXT：找到k=1，right_sum=0，调整后得到[2, 0, 1, 0]
• 第三次调用NEXT：找到k=2，right_sum=0，调整后得到[2, 0, 0, 1]
• 第四次调用NEXT：找到k=0，right_sum=1，调整后得到[1, 2, 0, 0]
• ...以此类推，完全匹配你给出的组合顺序。

额外说明 #

• 内存效率：这个算法只需要保存当前组合，内存复杂度为O(N)，不需要预存所有组合，非常适合N或X较大的场景。
• 完整性：每个组合都会被生成且仅生成一次，不会出现重复或遗漏。
• 扩展到正整数组合：如果需要所有元素都是正整数（即每个元素≥1），只需要先将X减去N（每个元素至少1），生成非负整数组合后，每个元素加1即可，同样适用这个算法。

内容的提问来源于stack exchange，提问作者Vojtech