Python递归函数中列表可变性问题及无连续1二进制字符串生成

def generateString_list_broken(N: int):
    def helper(i, n, arr, an):
        if i == n:
            an.append(arr.copy()) # 注意这里的arr.copy()是正确的，但之前的操作是错误的根源
            return 

        # 错误：i-1索引可能越界，且对arr的修改没有正确回溯
        if arr[i-1] == 1: 
            arr.append(0)
            helper(i+1, n, arr, an)
        if arr[i-1] == 0:
            arr.append(0)
            helper(i+1, n, arr, an)
            arr.pop() # 试图回溯，但位置不对，且缺少对1分支的回溯
            arr.append(1)
            helper(i+1, n, arr, an)       

    a = [0] 
    ans = []
    helper(1, N, a, ans) # 从[0]开始
    a = [1]
    helper(1, N, a, ans) # 从[1]开始
    return ans

# print(generateString_list_broken(3))
# output : [[0, 0, 0], [0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1], [1, 0, 0], [1, 0, 1]] (不正确)

def generateString_string_correct(N: int):
    def helper(i, n, arr, an):
        if i == n:
            an.append(arr)
            return

        if arr[i-1] == "1":
            arr += "0" # 创建新字符串
            helper(i+1, n, arr, an)
        if arr[i-1] == "0":
            arr += "0" # 创建新字符串
            helper(i+1, n, arr, an)
            arr = arr[:-1] # 创建新字符串，回溯
            arr += "1" # 创建新字符串
            helper(i+1, n, arr, an)       

    a = "0"
    an = []
    helper(1, N, a, an) # 从"0"开始
    a = "1"
    helper(1, N, a, an) # 从"1"开始
    return an

# print(generateString_string_correct(3))
# output : ['000', '001', '010', '100', '101'] (正确)

def generateString_list_correct_v1(N: int):
    def helper(n, arr, an):
        # 终止条件：当列表长度达到N时，将当前列表的副本添加到结果中
        if len(arr) == N:
            an.append(arr.copy()) 
            return 

        # 尝试添加 '0'
        arr.append(0)
        helper(n, arr, an)
        arr.pop() # 回溯：移除刚才添加的 '0'

        # 尝试添加 '1' (只有当上一个元素不是 '1' 时才允许)
        # arr[-1] 是当前刚刚pop掉的，所以需要检查arr[-1]
        # 或者更准确地说是arr[-1]在pop之前的值，即arr[-2]
        if arr[-1] == 0: # 检查当前列表的最后一个元素（即上一个递归层添加的元素）
            arr.append(1)
            helper(n, arr, an)
            arr.pop() # 回溯：移除刚才添加的 '1'

    ans = []
    # 从初始状态 [0] 和 [1] 分别开始
    helper(N, [0], ans)
    helper(N, [1], ans)
    return ans

print("--- 显式回溯 (方式一) ---")
print(generateString_list_correct_v1(3))
# Output: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]

def generateString_list_correct_v2(N: int):
    def helper(n, arr, an):
        if len(arr) == N:
            an.append(arr.copy())
            return 

        # 尝试添加 '0'
        arr.append(0)
        helper(n, arr, an)
        arr.pop() # 回溯

        # 尝试添加 '1'
        # 只有当列表为空（初始状态）或前一个元素是 '0' 时，才能添加 '1'
        if not arr or arr[-1] == 0: 
            arr.append(1)
            helper(n, arr, an)
            arr.pop() # 回溯

    ans = []
    helper(N, [], ans) # 从空列表开始
    return ans

print("\n--- 显式回溯 (方式二 - 单一初始调用) ---")
print(generateString_list_correct_v2(3))
# Output: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]

def generateString_list_correct_v3(N: int):
    def helper(n, arr, an):
        if len(arr) == N:
            an.append(arr.copy()) # 保存副本
            return

        # 尝试添加 '0'
        helper(n, arr + [0], an) # 传递新列表 arr + [0]

        # 尝试添加 '1'
        # 只有当列表为空（初始状态）或前一个元素是 '0' 时，才能添加 '1'
        if not arr or arr[-1] == 0:
            helper(n, arr + [1], an) # 传递新列表 arr + [1]

    ans = []
    helper(N, [], ans) # 从空列表开始
    return ans

print("\n--- 创建新列表 (避免原地修改) ---")
print(generateString_list_correct_v3(3))
# Output: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]