在回溯中记住列表

问：

我正在研究一个问题，该问题要求我生成一个包含所有差异值的数组。回溯自然似乎是这里使用的方法，但我在回溯的基本原理方面存在一些问题。 每个节点上都有一个 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: #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)

[子空间的照片，如果它有帮助][1]

[1]：https://i.stack.imgur.com/FC7DP.jpg 盒装列表是 choiceLists。

我遇到的主要问题是在 [0,1,2,5,6] 节点回溯后，ChoiceList 变为空。我希望它恢复到当时的样子。因此，当从 [0,1,2,5,6] 回溯到 [0,1,2，None，6] 时，它应该检测到由于 choiceList 为空，因此此处的所有可能组合都已被探索，并且应该再次回溯到 [0,1，None，None，6]，这里 choiceList 应该恢复为 {2,3,4,5} - {2} = {3,4,5}，因为到目前为止{2}一直使用。

我意识到我没有说得很清楚，我很抱歉。我需要的是有关如何在此类问题中执行回溯的见解？

编辑- 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