递归代码处理字符串正常但传入列表参数时失效问题排查

问题根源 #

列表版本代码出错的核心原因是可变对象的回溯处理不完整，以及分支逻辑的互斥性缺失：

1. 回溯遗漏：列表是可变类型，arr.append(0)会直接修改原列表。当arr[i-1] == 1的分支执行完递归后，没有对列表进行pop()回溯，导致后续分支使用的是被修改后的列表，序列长度异常。
2. 分支逻辑冲突：两个独立的if分支会依次执行——当第一个分支修改列表后，第二个分支的判断条件可能从arr[i-1] ==1变成arr[i-1] ==0，触发多余的递归操作，生成不符合长度要求的序列。

而字符串版本能正常工作，是因为字符串是不可变类型，arr += "0"会创建新字符串，原字符串不受影响，无需手动回溯，自然不会污染递归上下文。

修正方案 #

通过补全回溯操作、调整分支为互斥逻辑，修复后的代码如下：

def generateString(N: int):
    def helper(i, n, arr, ans):
        if i == n:
            ans.append(arr.copy())
            return
        last = arr[-1]  # 直接取最后一个元素，避免i与列表长度不匹配的问题
        if last == 1:
            arr.append(0)
            helper(i+1, n, arr, ans)
            arr.pop()  # 回溯，恢复原列表状态
        else:  # last ==0 的情况，用else保证分支互斥
            arr.append(0)
            helper(i+1, n, arr, ans)
            arr.pop()
            arr.append(1)
            helper(i+1, n, arr, ans)
            arr.pop()  # 回溯添加的1
    ans = []
    helper(1, N, [0], ans)
    helper(1, N, [1], ans)
    return ans

print(generateString(3))
# 输出: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]

关键修正点 #

• 将两个独立if改为if-else，确保同一递归层级只会执行一个分支，避免逻辑冲突。
• 每个append操作后的递归调用完成后，立即执行pop()回溯，恢复列表到调用前的状态，保证后续递归使用正确的序列上下文。
• 用arr[-1]替代arr[i-1]，更直观地获取序列最后一个元素，避免因列表修改导致的索引与长度不匹配问题。

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