Python回溯算法中递归全局变量问题及替代方案咨询

嘿，我来逐个拆解你遇到的这些问题：

1. 全局列表定义与global关键字报错问题 #

你碰到的global name 'res' is not defined错误，大概率是因为**global声明的位置不对**，或是在某些运行环境里变量作用域的解析出了小问题。其实对于列表这种可变对象，如果你只是做原地修改（比如append、pop），哪怕不声明global也能访问全局变量——前提是你没在函数内部重新赋值这个变量（比如写res = []会创建局部变量，直接覆盖全局的res）。

如果确实要用到全局变量，规范的做法是把global res放在函数的最开头（任何使用该变量的代码之前），比如：

seen = []
res = []

def func(candidates, k, anc_choice):
    global res  # 放在函数开头，让解析器明确要调用全局的res
    # ... 后续代码不变

不过全局变量并不是回溯算法的最优解，接下来咱们说更稳妥的方案。

2. 无需全局变量获取结果的通用方法 #

当然有！最常用的两种思路：

• 将结果列表作为参数传递：递归调用时把结果列表传入函数，每次找到符合条件的组合就直接添加进去。这种方式没有全局变量的副作用，也更符合函数式编程的逻辑。
• 用函数返回值收集结果：让递归函数返回当前分支下找到的所有组合，在父调用里把这些结果合并起来。

举个参数传递的改造示例：

def func(candidates, k, anc_choice, res):
    if sum(anc_choice) == k:
        # 这里要复制列表，后面会解释原因
        res.append(list(anc_choice))
        return
    for c in candidates:
        if sum(anc_choice) + c <= k:  # 提前判断，减少不必要的递归
            anc_choice.append(c)
            func(candidates, k, anc_choice, res)
            anc_choice.pop()

# 调用时初始化结果列表
res = []
func([2,3,6,7], 7, [], res)
print(res)

3. res.append(anc_choice)无法得到正确结果的原因 #

这是回溯里非常容易踩的坑：你添加到res里的是anc_choice这个列表对象的引用，而不是它当前内容的副本。

递归过程中，你一直在对同一个anc_choice列表做append和pop操作，等递归结束后，这个列表已经被还原到初始状态了。所以最后res里的所有元素指向的都是同一个空（或最终状态）的列表，自然看不到正确结果。

解决办法很简单：添加的时候创建列表的副本，比如：

res.append(list(anc_choice))  # 或者用 anc_choice.copy()、[x for x in anc_choice]

另外，你用seen集合去重的方式也有隐患：比如[2,2,3]的集合是{2,3}，如果后续生成类似[2,3,2]的组合（虽然当前逻辑不会，但候选集有重复元素时就会出问题），集合会误判为同一组合。更好的去重方式是先给候选集排序，然后递归时限制只能选择当前索引及之后的元素，从根源避免生成重复组合：

def func(candidates, k, start, anc_choice, res):
    if sum(anc_choice) == k:
        res.append(list(anc_choice))
        return
    for i in range(start, len(candidates)):
        # 跳过重复元素（候选集有重复时生效）
        if i > start and candidates[i] == candidates[i-1]:
            continue
        if sum(anc_choice) + candidates[i] <= k:
            anc_choice.append(candidates[i])
            # 下一次递归从i开始，避免回头选前面的元素，杜绝排列组合
            func(candidates, k, i, anc_choice, res)
            anc_choice.pop()

candidates = [2,3,6,7]
candidates.sort()  # 先排序
res = []
func(candidates, 7, 0, [], res)
print(res)

这样改造后，既能正确收集结果，又能高效避免重复组合，不需要额外的seen集合。

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