Python递归中使用字典缓存（memo）为何引发结果错误？

问题根源：可变对象的引用传递 #

Python中列表是可变对象，当你把列表存入memo缓存时，存的不是列表的副本，而是指向该列表的内存引用。后续对这个列表的修改（比如lis.insert(0, word)）会直接影响memo中存储的内容——因为它们指向同一个内存地址。

具体到你的代码执行流程：

1. 首次处理target='le'时，返回[['le']]并存入memo，此时memo['le']指向这个列表。
2. 处理target='ple'时，匹配前缀'p'，调用allConstruct('le', ...)从memo取出的是[['le']]的引用。执行lis.insert(0, 'p')后，原列表变成['p', 'le']，memo中的'le'也同步变成这个值。
3. 后续处理'purple'的其他路径时，取出的'le'缓存已经是被修改后的列表，继续插入'purp'会导致memo['le']变成['p', 'purp', 'le']，最终所有依赖这个缓存的结果都被污染。

修复方案：避免修改缓存中的可变对象 #

不要直接修改从缓存中取出的列表，而是创建新列表来存储拼接结果。修改代码中处理suffixways的部分：

def allConstruct(target,wordBank, memo=None):    
    if memo is None: memo={}
    if target in memo: return memo[target]
    if target=='': return [[]]

    can=[]
    for word in wordBank:
        if target.find(word)==0 :
            suffix=target[len(word):]
            suffixways=allConstruct(suffix,wordBank,memo)
            # 创建新列表存储拼接结果，不修改原缓存列表
            target_ways = [[word] + lis for lis in suffixways]
            can.extend(target_ways)
    memo[target]=can

    return can
print(allConstruct('purple',['purp','p','ur','le','purpl']))

运行后会得到正确结果：[['purp', 'le'], ['p', 'ur', 'p', 'le']]，memo中的值也不会被篡改。

如果一定要使用insert方法，需要先复制原列表再修改，避免直接操作缓存引用：

for lis in suffixways:
    new_lis = lis.copy()  # 或 list(lis) 创建副本
    new_lis.insert(0, word)
    can.append(new_lis)

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