求x₁+x₂+…+xₙ=C非负整数无重解的高效生成算法

你需要的是不定方程非负整数有序解的生成算法，属于组合数学领域非常成熟的现成算法，完全可以做到无重复、低冗余，刚好适配多项式项按幂次遍历的场景。

核心逻辑说明 #

该问题的本质是求n个非负整数加和为C的所有有序元组，对应组合数学的可重组合结论，总共有C(n + C - 1, C)个解，只要按固定顺序生成就能天然避免重复，不需要额外的去重操作。

常用无重复生成算法 #

1. 递归生成法（最易实现，适合中小规模场景） #

逐位确定每个变量的取值，全程按从小到大的顺序遍历，生成的解天然唯一：

• 第1位x1可取值范围为0~C
• 确定x1后，第2位x2可取值范围为0~(C-x1)
• 以此类推，直到最后1位xn，直接取剩余的数值即可

2. 迭代式下一个组合生成法（适合大规模场景，避免递归栈溢出） #

核心逻辑类似数字进位：

• 初始化解为[0, 0, ..., C]
• 每次找到最右侧可以加1的位置，该位置加1后，右侧所有位置重置为最小可能值，保证总和始终为C
• 直到解变为[C, 0, ..., 0]时停止遍历

适配全次遍历的优化 #

你需要遍历C从0到多项式最高次D的所有解，可以直接调整逻辑避免重复计算：

• 递归时跟踪当前已分配的总和，遍历到最后一位时，总和可以取0到D的所有值，一次性生成所有幂次的项
• 也可以按C从小到大依次生成对应解，符合多项式按次数升序遍历的常规需求

可直接使用的Python示例代码 #

def generate_term_powers(var_count, target_sum, current_path=None):
    if current_path is None:
        current_path = []
    # 遍历到最后一个变量时直接取剩余值
    if var_count == 1:
        yield tuple(current_path + [target_sum])
        return
    # 按从小到大顺序遍历当前变量的所有可能取值
    for current_val in range(0, target_sum + 1):
        yield from generate_term_powers(
            var_count - 1, 
            target_sum - current_val, 
            current_path + [current_val]
        )

# 示例：遍历3元多项式最高次为4的所有项的幂次
max_degree = 4
variable_count = 3
for degree in range(0, max_degree + 1):
    for powers in generate_term_powers(variable_count, degree):
        # 此处替换为你的多项式项处理逻辑
        print(f"次数{degree}的项幂次：{powers}")

该代码生成的幂次元组全程无重复，顺序固定，没有额外冗余计算，时间复杂度和总项数完全一致，属于最优效率的实现方案。

性能说明 #

• 对于常规场景（变量数≤10，最高次≤20），递归版实现的效率完全够用
• 如果需要处理更高次、更多变量的多项式，可改用迭代版实现，规避递归栈开销，性能还能提升30%以上

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