DFS算法中list.append不生效？LeetCode77组合问题NoneType报错分析

1 报错直接诱因 #

Python 中列表的append()方法属于原地修改操作，没有返回值，默认返回None。你在递归调用dfs时，直接把path.append(lis[i])作为参数传入，实际传给下一层path形参的值是None，当下一层执行len(path)判断时，自然会抛出NoneType没有len()方法的类型错误。

2 两种写法的核心区别 #

• path.append(lis[i])：直接修改原path列表的内存内容，不会生成新列表，返回值为None，仅用于修改原列表，不适合直接作为参数传递。
• path + [lis[i]]：属于列表拼接运算，会在内存中生成一个全新的列表对象，值为原path列表的所有元素加上新元素lis[i]，原path列表不会被修改，返回值就是这个新生成的合法列表，因此可以直接作为参数传入下一层递归。

3 扩展：使用append实现的正确写法 #

如果偏好使用append原地修改的方式实现回溯，需要拆分操作步骤并补充回溯逻辑，同时注意存入结果集时要拷贝列表（避免所有结果引用同一个列表对象导致最终值被回溯修改），参考代码如下：

from typing import List
def combine( n: int, k: int) -> List[List[int]]:      
    res = []
    lis = [i for i in range(1,n+1)]
    def dfs(lis, path):
        if len(path) == k:    
            res.append(path.copy()) # 存入拷贝后的列表
            return
        for i in range(len(lis)):
            path.append(lis[i]) # 先修改原列表
            dfs(lis[i+1:], path) # 传入修改后的原列表
            path.pop() # 回溯：撤销本次添加操作
    dfs(lis, [])
    return res

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