Python中DFS代码执行时ans列表为何在lst.pop()后被修改？

问题场景 #

当输入N=4、M=1时，调用lst.pop()后，ans列表的内容出现类似“重置”的变化。原以为ans和lst是两个独立的列表，无法理解该现象，寻求解答。

原代码 #

N,M=map(int,input().split())

ans=[]
lst=[]

def dfs(num):
    global ans
    if(num==M):
        ans.append(lst)
        return

    for i in range(1,N+1):
        if(i not in lst):
            lst.append(i)
            dfs(len(lst))
            print(ans)
            lst.pop()
            print(ans)

dfs(0)

print(ans)

问题原因 #

Python中列表属于引用类型，你执行ans.append(lst)时，并没有把lst的内容复制一份存入ans，而是把lst这个对象的引用添加到了ans里。也就是说，ans中的所有元素其实都指向同一个lst对象。

当你调用lst.pop()修改lst时，这个唯一的lst对象的内容发生了变化，ans里保存的引用自然会同步显示出这个变化，看起来就像ans被“重置”了。

解决方法 #

往ans中添加lst的独立副本，而不是原引用。可以通过以下两种方式实现：

• 使用lst.copy()方法创建副本
• 使用切片lst[:]生成副本

修改后的关键代码如下：

if(num==M):
    ans.append(lst.copy())  # 或 ans.append(lst[:])
    return

修改后，输入N=4、M=1时，ans最终会正确保存[[1], [2], [3], [4]]，后续修改lst不会再影响ans中的内容。

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