我理解的回溯法回溯法本质上是一种穷举法。对于穷举法的优化，优化的关键是判断哪些情况不需要考虑，然后不要去遍历这些不需要的情况。必要的（修剪）。要理解穷举法，理解回溯法，首先要真正理解穷举法。使用下面的例子来理解穷举法输出的数字的完整排列输入：123输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]核心步骤的伪代码：Permutation(arrayA,arrayB){IfArrayBisOKReturnarrayAElseForIinB:Permutation(AaddI,BremoveI)}Python实现：#FullPermutationfullarrangementdefpermute(numbers:list):sorted(numbers)visited=[0foriinnumbers]output=[]middle=[]helper(numbers,visited,middle,output)returnoutputdefhelper(numbers:list,visited:list,middle:list,output:list):如果len(middle)是len(numbers):output.append(middle.copy())returnforiinrange(0,len(numbers)):如果visited[i]为0:visited[i]=1middle.append(numbers[i])helper(numbers,visited,middle,output)visited[i]=0middle.pop()if__name__=='__main__':nums=[1,2,3]print(permute(nums))N皇后问题，这个在回溯法中比较经典，大家理解exhausted全排列法，可以试着理解N皇后问题，其实全排列实现也是用return回到思路，我们以8个皇后为例，在8*8的棋盘上，放置8个皇后的棋子，使其不能在同一行且对角。输入：8输出：92Python实现：#Nqueennqueenproblemdefn_queens(n:int):output=[0]middle=[-1foriinrange(0,n)]compute_n_queen(n,0,middle,output)returnoutput[0]defcompute_n_queen(n:int,row:int,middle:list,output:list):如果n是行：output[0]+=1return#linebylineforcolumninrange(0,n):flag=1middle[row]=column#这里检查之前放的块和这次放的块是否冲突，也就是回溯法forjinrange(0,row)的剪枝:#因为我们是逐行判断的，所以不需要判断是否在同一行，只判断是否在同一列#是否在同一对角线判断减法和加法是否如果middle[row]是middle[j]或row-middle[row]是j-middle[j]或row+middle[row]是j+middle[j]则行和列相同：flag=0breakif标志：compute_n_queen(n,row+1,middle,output)if__name__=='__main__'：打印（n_queens（8））
