如何高效实现对元素和为k的n元非负整数组的遍历？

你的问题本质是组合数学中的星号与横杆问题，符合条件的元组总数为组合数C(n+k-1, k)。朴素遍历的O(kⁿ)时间复杂度显然低效，下面提供两种按需生成、无需存储所有组合的高效遍历方法：

方法一：递归生成器（内存友好，实现简单） #

通过递归逐个枚举每个位置的可能取值，生成器会在需要时产出单个元组，不会一次性占用大量内存存储所有组合。

思路 #

1. 对于长度为1的元组，直接返回仅包含剩余和的元组；
2. 对于长度>1的元组，枚举第一个元素的所有可能取值（0到当前剩余和k），然后递归生成剩余n-1个元素，使其和为k减去当前第一个元素的值；
3. 将当前元素与递归得到的剩余元组拼接，逐个产出。

代码示例（Python） #

def generate_tuples(n, k):
    if n == 1:
        yield (k,)
        return
    # 枚举第一个元素的所有可能取值
    for m in range(k + 1):
        # 递归生成剩余n-1个元素，和为k - m
        for rest_tuple in generate_tuples(n - 1, k - m):
            yield (m,) + rest_tuple

# 使用示例：遍历n=2、k=2的所有符合条件的元组
for t in generate_tuples(2, 2):
    print(t)

方法二：迭代式"下一个元组"生成（无递归，适合大规模场景） #

通过字典序的迭代规则，逐个生成下一个符合条件的元组，无需递归调用，适合n和k较大的场景。

思路 #

1. 初始元组设为(k, 0, 0, ..., 0)；
2. 从右往左找到第一个非零元素的位置i（i < n-1）；
3. 将m_i减1，把m_{i+1}设为「原m_{i+1}到m_n的和 + 1」，并将i+2到n的元素设为0；
4. 重复步骤2-3，直到生成(0, 0, ..., k)后终止。

代码示例（Python） #

def next_valid_tuple(current):
    n = len(current)
    # 从右向左查找第一个可调整的非零元素（排除最后一位）
    for i in range(n-2, -1, -1):
        if current[i] > 0:
            new_t = list(current)
            new_t[i] -= 1
            # 计算右侧需要分配的总和
            rest_sum = sum(current[i+1:]) + 1
            new_t[i+1] = rest_sum
            # 右侧其余元素置0
            for j in range(i+2, n):
                new_t[j] = 0
            return tuple(new_t)
    return None  # 所有元组已生成完毕

# 使用示例：遍历n=3、k=2的所有符合条件的元组
current = (2, 0, 0)
while current is not None:
    print(current)
    current = next_valid_tuple(current)

说明 #

两种方法的时间复杂度均为O(C(n+k-1, k))，这是遍历所有符合条件元组的最优复杂度（因为必须访问每个元组一次）。内存方面，仅需存储当前正在处理的单个元组，内存占用为O(n)，远优于朴素方法的O(kⁿ)。

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