回溯算法递归中为何需要复制数组元素才能得到正确结果

这个问题本质是Python的可变对象引用机制导致的，和回溯逻辑本身无关：

• 整个递归流程中，你自始至终只创建了1个temp列表对象，所有append、pop操作都是在原地修改这同一个列表，没有生成新的列表
• 列表属于可变引用类型，如果直接写res.append(temp)，存入结果集的不是当前temp里的元素快照，而是temp这个对象的内存地址引用
• 整个递归执行完后，所有回溯的pop操作会把temp清空回初始的空列表状态。由于res里存的全是指向这同一个temp的引用，最终你读取res的时候，所有元素都会跟着变成空数组，自然拿不到正确的子集。

temp.copy()做的是浅拷贝操作：它会生成一个全新的列表对象，把当前temp里存储的元素复制到新对象中，再把这个新对象存入res。后续temp做任何append、pop修改，都不会影响之前已经存入res的独立列表，因此能正确保留每个递归终止节点的子集状态。

对应正确实现代码如下：

def subsets(self, nums: List[int]) -> List[List[int]]:
        res = list()
        temp = list()
        def dfs(nums,i):
            if i==len(nums):
                res.append(temp.copy())
                return
            temp.append(nums[i])
            dfs(nums,i+1)
            temp.pop()
            dfs(nums,i+1)
        dfs(nums,0)
        return res

可以做个简单验证：去掉copy逻辑后，在每次append temp后打印res的内容，你会发现每次修改temp，res里之前存的所有元素都会同步变化，这就是引用同一个对象的典型表现。

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