Python递归回溯中如何全局存储变量及临时列表？

首先，你遇到的核心问题是可变对象的引用传递导致的：

在你的代码中，li2是一个列表（可变对象），当你调用adg(li2)时，传递的是这个列表的引用，而不是它的副本。adg函数里avc.append(li3)实际上是把这个引用添加到了avc中。但在递归回溯的过程中，你会执行li2.remove(li[i])来修改这个列表——所有指向这个列表的引用都会看到这个修改。当整个递归结束后，li2已经被清空了，所以avc里存储的所有引用指向的都是同一个空列表，这就是最后打印avc为空的原因。

而在line x处打印li2正常，是因为此时还没执行后续的li2.remove(li[i])操作，列表里的元素还没被移除。

解决方法 #

要解决这个问题，只需要在adg函数中添加li2的副本到avc，而不是添加引用。Python中可以通过以下几种方式创建列表副本：

• 使用li3.copy()方法
• 使用切片li3[:]
• 使用list(li3)构造函数

修改后的adg函数如下：

def adg(li3):
    global avc
    avc.append(li3.copy())  # 或者 avc.append(li3[:]) / avc.append(list(li3))
    # print("avc",avc)

关于递归中变量存储的补充说明 #

你提到的递归调用中变量存储的问题：每个递归调用都会创建自己的栈帧，栈帧里包含该次调用的局部变量。但在你的代码中，li2是作为参数传递进来的，所有递归调用操作的是同一个列表对象——这正是回溯法的核心：在进入下一层递归前修改列表，返回后再撤销修改（回溯）。但如果要保存当前状态的结果，必须保存副本，否则后续的回溯操作会覆盖你想要保留的结果。

完整修改后的代码示例 #

avc=[]
var=0
def func(li,n,sumo,li2):
    if sumo==n:
        global var
        var+=1
        # print(li2) ##line x
        adg(li2)
        return
    elif sumo>n:
        return
    else:
        for i in range(0,len(li)):
            li2.append(li[i])
            sumo=sum(li2)
            func(li,n,sumo,li2)
            li2.remove(li[i])
def adg(li3):
    global avc
    avc.append(li3.copy())  # 这里创建副本
    # print("avc",avc)
if __name__=="__main__" :
    liq=list(map(int,input().strip().split()))
    n=liq[0]
    li=list(map(int,input().strip().split()))
    func(li,n,0,[])
    print(avc)

这样修改后，avc中就会保存每次满足条件时li2的独立副本，不会被后续的回溯操作影响，最后打印avc就能得到正确的结果了。

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