回溯算法中ChoiceList状态记忆问题及实现修正咨询

我需要生成包含所有差值的数组，采用回溯算法实现，但遇到核心问题：每个节点对应一个ChoiceList，选取元素并校验条件后，当叶子节点校验失败回溯时，无法恢复该节点原本的ChoiceList状态。例如从[0,1,2,5,6]回溯到[0,1,None,None,6]时，ChoiceList应恢复为{3,4,5}，但当前代码回溯后ChoiceList为空，导致后续流程无法按预期执行。

实现代码 #

def arrayGen(n,N,proto,choiceList,i):
    proto[-1] = N

    if None not in proto:
        lst = diffChecker(proto)
        if 0 in lst or 1 in lst: #now we backtrack
            print(f"{proto} is not a solution\n")
            return
        else:
            print(f"{proto} is a solution\n")
            return

    if not choiceList: #choicelist is empty
        print(f"{proto} contains None\n")
        return

    if proto[i] is None:
        proto[i] = choiceList[0]
        choiceList.pop(0)
        arrayGen(n,N,proto,choiceList,i+1)
        proto[i] = None
        arrayGen(n,N,proto,choiceList,i)
    else:
        arrayGen(n,N,proto,choiceList,i+1)

diffChecker函数 #

def diffChecker(lst):
    result = [0]*(lst[-1]+1)
    dontCount = set()
    result[0] = 2
    result[-1] = 2
    for i in range(1,lst[-1]):#diff_Values
        dontCount = set()
        for j in lst:
            if j == None:
                continue
            if((j + i) in lst and frozenset((j,j+i)) not in dontCount):
                result[i] += 1
                dontCount.add(frozenset((j,j+i)))
            elif((j-i) in lst and frozenset((j,j-i)) not in dontCount):
                result[i] += 1
                dontCount.add(frozenset((j,j-i)))
    return result

驱动代码 #

#driver/main code-
n = int(input("Enter array size: "))
N = n+1 # dynamic upper limit
proto = [None]*n #length of resultant array is fixed
proto[0] = 0 #first element is always 0
proto[-1] = N
diff_table = [0]*(N+1)
diff_table[-1] = 2 #in actuality it is 1, but for efficiency purposes we've put = 2
diff_table[0] = 2
current_diff = 1 # since diff val of 0 is already present twice - (0-0) & (N-N)
choiceList = []
for i in range(1,N):
    choiceList.append(i)
i = 0
arrayGen(n,N,proto,choiceList,i)

当前输入输出示例 #

Enter array size: 5
#now, we try to generate all array combinations that satisfy the diffChecker function from this via backtracking

[0, 1, 2, 3, 6] is not a solution

[0, 1, 2, 4, 6] is not a solution


[0, 1, 2, 4, 6] is not a solution

[0, 1, 2, 5, 6] is not a solution


[0, 1, 2, None, 6] contains None

[0, 1, None, None, 6] contains None
#from this part on, the code should not backtrack again. Refer to the attached picture on how exactly I'm trying to fill up the None spots

#expected- [0,1,3,None,None,6] ->(advance) [0,1,3,4,None,6] ->....

[0, None, None, None, 6] contains None

问题核心原因 #

当前代码的关键错误是直接修改了共享的ChoiceList对象：列表是可变类型，函数传参为引用传递，所有递归分支共享同一个ChoiceList实例。执行choiceList.pop(0)后，原列表的元素被永久移除，回溯时没有任何操作恢复这些元素，导致后续节点的ChoiceList为空，无法继续生成新的组合。

解决思路 #

1. 传递列表副本（推荐）

每次递归时创建ChoiceList的副本，移除当前选中的元素后传给下一层递归，原列表保持不变。这样回溯时无需手动恢复状态，因为原列表从未被修改。同时，遍历所有可选元素而非仅取第一个，确保覆盖所有可能的组合。

修改后的arrayGen函数示例：

def arrayGen(n,N,proto,choiceList,i):
    proto[-1] = N

    if None not in proto:
        lst = diffChecker(proto)
        if 0 in lst or 1 in lst:
            print(f"{proto} is not a solution\n")
            return
        else:
            print(f"{proto} is a solution\n")
            return

    if not choiceList:
        print(f"{proto} contains None\n")
        return

    if proto[i] is None:
        # 遍历所有可选元素，尝试每一种可能
        for idx, val in enumerate(choiceList):
            proto[i] = val
            # 创建新的ChoiceList副本，排除当前选中的元素
            new_choice = choiceList[:idx] + choiceList[idx+1:]
            arrayGen(n,N,proto,new_choice,i+1)
            # 回溯：恢复proto[i]的状态
            proto[i] = None
    else:
        arrayGen(n,N,proto,choiceList,i+1)

2. 手动恢复ChoiceList状态

如果坚持修改原列表，需在递归返回后，将之前移除的元素重新插入到ChoiceList的原位置，恢复到修改前的状态：

def arrayGen(n,N,proto,choiceList,i):
    proto[-1] = N

    if None not in proto:
        lst = diffChecker(proto)
        if 0 in lst or 1 in lst:
            print(f"{proto} is not a solution\n")
            return
        else:
            print(f"{proto} is a solution\n")
            return

    if not choiceList:
        print(f"{proto} contains None\n")
        return

    if proto[i] is None:
        # 取出第一个元素，保存值
        val = choiceList.pop(0)
        proto[i] = val
        arrayGen(n,N,proto,choiceList,i+1)
        # 回溯：恢复proto和ChoiceList的状态
        proto[i] = None
        choiceList.insert(0, val)
    else:
        arrayGen(n,N,proto,choiceList,i+1)

注：这种方式仅处理第一个元素的分支，若要覆盖所有组合，仍需改为遍历所有元素的逻辑，因此更推荐第一种传递副本的方式。

3. 优化选择逻辑

原代码仅尝试ChoiceList的第一个元素，导致大部分可能的组合被忽略。通过遍历ChoiceList的所有元素，才能生成所有符合条件的数组组合，这是回溯算法覆盖所有解的核心要求。

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