LeetCode 78子集问题运行输出全为空列表的原因排查

问题根因 #

故障核心是Python列表为可变引用类型，代码中向output追加元素时，存入的始终是同一个el列表的内存引用，而非递归到终止条件时el的内容快照。
整个递归回溯流程中，代码始终在操作同一个初始创建的el列表：选中当前元素时执行append，回溯时执行remove删除元素。等全部递归逻辑执行完成后，这个全局复用的el列表已经被清空，而output中存储的8个引用全部指向这同一个空列表，最终打印结果就会出现8个空列表。

修复方法 #

在递归终止、存储结果的位置，追加el列表的浅拷贝，而非直接存入原列表引用即可。另外回溯删除元素时用pop()替代remove()效率更高：因为刚追加的元素一定在列表末尾，pop()是O(1)操作，remove()需要遍历列表查找对应值，时间复杂度更高。
修复后的完整代码：

def addsubsets(nums,el,i,n):
    if i == n:                    
        # 存入el的副本，切断和后续回溯操作的关联
        output.append(el.copy())
        return

    el.append(nums[i])
    addsubsets(nums, el, i+1, n)
    el.pop()
    addsubsets(nums, el, i+1, n)
        
output = []                
nums = [1,2,3]
addsubsets(nums, [], 0, len(nums))   
print(output)

运行上述代码输出为[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]，与预期结果完全匹配。

补充说明 #

• 原代码中el.remove(nums[i])的写法在本题nums元素全唯一的前提下不会出现逻辑错误，但如果存在重复元素，remove()只会删除第一个匹配值，会导致回溯删错元素的问题，用pop()删除末尾元素是回溯算法的标准写法。
• 除了el.copy()，也可以用el[:]切片的方式生成列表浅拷贝，效果完全一致。

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