生成方程x1+x2+…+xk=n所有非负解的算法（星与条法及回溯实现）

核心思路 #

回溯法的本质是逐步构建解空间，尝试所有可能的取值组合，具体到这个问题：

• 按顺序为每个变量xᵢ确定取值，从x₁到xₖ；
• 对于第i个变量，它的取值范围是0到剩余未分配的总和（因为后续变量必须非负，所以当前变量最多取剩下的所有值）；
• 当处理到最后一个变量时，它的值直接等于剩余总和，此时得到一个完整的解，记录下来即可。

代码实现（Python） #

def generate_non_negative_solutions(k, n):
    solutions = []
    
    def backtrack(index, current_solution, remaining):
        # 处理到最后一个变量，直接赋值剩余值
        if index == k - 1:
            current_solution.append(remaining)
            solutions.append(current_solution.copy())
            current_solution.pop()  # 回溯
            return
        
        # 当前变量可以取0到remaining的所有值
        for value in range(0, remaining + 1):
            current_solution.append(value)
            # 递归处理下一个变量，剩余值减去当前取值
            backtrack(index + 1, current_solution, remaining - value)
            current_solution.pop()  # 回溯，尝试下一个取值
    
    backtrack(0, [], n)
    return solutions

# 示例：k=3，n=2
if __name__ == "__main__":
    k = 3
    n = 2
    result = generate_non_negative_solutions(k, n)
    print(f"方程x₁+x₂+x₃=2的所有非负整数解：")
    for sol in result:
        print(sol)

代码解释 #

• backtrack函数是核心递归逻辑：
  • index：当前处理的变量下标（从0开始，对应x₁到xₖ）；
  • current_solution：当前正在构建的解列表；
  • remaining：还未分配的总和，初始为n；
• 当index等于k-1（最后一个变量），直接将remaining加入解列表，保存副本后回溯；
• 循环遍历当前变量的所有可能取值，加入解列表后递归处理下一个变量，递归返回后弹出当前取值，继续尝试下一个可能。

示例输出 #

运行上述代码会得到：

方程x₁+x₂+x₃=2的所有非负整数解：
[0, 0, 2]
[0, 1, 1]
[0, 2, 0]
[1, 0, 1]
[1, 1, 0]
[2, 0, 0]

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