Python回溯两种curr操作方式导致全局ans结果差异原因咨询

在实现n选k的组合回溯逻辑时，向当前路径列表curr追加元素有两种常见写法，运行结果完全不同，具体对比如下：

可得到正确结果的写法 #

n = 4
k = 2
ans = []
def backtrack(first, curr):
    if len(curr)==k:
        ans.append(curr)
    for i in range(first, n+1):
        # curr.append(i)
        backtrack(i+1, curr+[i])
        # curr.pop()

curr = []
backtrack(1, curr)
print("result = ",ans)

运行输出：
result = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

输出全空列表的错误写法 #

n = 4
k = 2
ans = []
def backtrack(first, curr):
    if len(curr)==k:
        ans.append(curr)
    for i in range(first, n+1):
        curr.append(i)
        backtrack(i+1, curr)
        curr.pop()

curr = []
backtrack(1, curr)
print("result = ",ans)

运行输出：
result = [[], [], [], [], [], []]

两种写法的本质差异与错误根因 #

两种写法结果不同的核心原因是Python中列表是可变对象，传参和赋值默认传递的是对象引用，不是对象的完整副本，具体区别：

• 正确写法中，递归传参用的curr+[i]会生成一个全新的独立列表，每一层递归分支拿到的curr都是互不干扰的新对象。当满足长度条件把curr存入ans时，存入的就是这个独立列表的当前值，后续其他递归分支的操作不会修改已经存入ans的列表内容，因此最终能得到正确的组合结果。
• 错误写法中，全程只操作了初始化时创建的那一个curr列表：append是原地给列表加元素，pop是回溯时原地移除元素。当满足长度条件执行ans.append(curr)时，实际存入ans的是指向这同一个curr列表的引用，并没有保存当时列表里的元素快照。等整个递归流程全部执行完，所有pop操作完成后，curr会回到初始的空列表状态，ans里存的6个引用全指向这个空列表，最终打印出来就全是空值。

如果要保留第二种原地修改curr的写法，只需要修改存入ans的逻辑，存列表的副本即可，比如把ans.append(curr)改成ans.append(curr[:])，就能得到正确结果。

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