Python回溯求解全排列：直接append(curr)为何返回空结果？

在求解全排列问题时，你会发现直接用ans.append(curr)会得到空结果，换成ans.append(curr[:])才返回正确答案，你的代码如下：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(curr):
            if len(curr) == len(nums):
                ans.append(curr)
                # ans.append(curr[:])
                return
            for num in nums:
                if num not in curr:
                    curr.append(num)
                    backtrack(curr)
                    curr.pop()

        ans = []
        backtrack([])
        return ans

问题根源：Python列表的引用特性 #

Python里的列表是可变对象，当你执行ans.append(curr)时，并没有把curr当前的内容复制一份存入ans，而是把curr这个列表的内存引用加进了ans。也就是说，ans里的所有元素其实都指向同一个列表对象。

在回溯过程中，每次递归返回后都会执行curr.pop()，这个操作会直接修改curr指向的那个列表。当整个回溯流程结束时，curr已经被一步步pop回空列表了，而ans里的所有元素都是这个空列表的引用，所以最终返回的ans全是空结果。

为什么curr[:]能解决问题？ #

curr[:]是Python里创建列表浅拷贝的常用写法，它会生成一个和curr当前内容完全相同的新列表。把这个新列表append进ans后，就算后续修改原curr，也不会影响已经存入ans的这个新列表——因为它们是两个独立的对象，内存地址不同。这样每次符合条件时，存入ans的都是curr当时状态的快照，最终就能得到正确的全排列结果。

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