【算法】（Python）回溯算法

回溯算法：

• 回溯算法是一种算法思想。
• 采用“深度优先搜索（dfs，depth first search）”。
• 采用“尝试”和“回溯”的策略。尝试搜索所有可能的解决方案，遇到不满足条件的撤销选择、回退到回溯点（满足回溯条件的某个状态的点）、尝试其他方法。
• 基本思想：从一条路往前走，能进则进，不能进则退回来，换条路再试。
• 类似穷举法，但有剪枝的功能。剪枝：去除不满足约束条件的尝试、提高效率。
• 通常用递归实现。（也可以用迭代实现，但设计复杂）

回溯算法的伪代码模板：

res = []                                 # 记录所有的最终解def traceback(各参数):if 终止条件：res.append(最终解)                # 保存结果returnfor 方案 in 所有可能的解决方案:          # 遍历所有可能的解决方案if 约束条件:                       # 剪枝做出选择，更新状态traceback(各参数)              # 递归搜索回溯，撤销选择，回退到上一状态traceback(各参数)                          # 执行函数

举例：

1、（难度：简单）【力扣】1863. 找出所有子集的异或总和再求和

解题思路：搜索所有组合，深度优先搜索。遍历给定列表中每个元素，选择该元素并往下递归搜索，再撤销选择，尝试其他搜索。最后所有组合的异或结果求和。

知识点：x ^ y：x和y进行异或运算。异或运算：二进制中各位依次比对，相同为0，不同为1。 

class Solution:def subsetXORSum(self, nums: List[int]) -> int:def traceback(i, xor):# 终止条件：遍历到列表结束if i == n:res.append(xor)      # 最终解保存到结果列表中return# 选择当前元素traceback(i + 1, xor ^ nums[i])# 撤销选择（即不选择当前元素）traceback(i + 1, xor)res = []            # 结果列表，存放所有组合的异或结果xor = 0             # 一个组合的异或结果i = 0               # 目前是列表中哪个元素n = len(nums)       # 列表长度traceback(i, xor)   # 执行函数return sum(res)

2、（难度：中等）【力扣】46. 全排列

 解题思路：全排列：每个元素都有，只是顺序不同。因此，两个列表：结果列表（存放所有组合），存放一个全排列组合的列表。依次往组合中添加元素，给定列表中的每个元素只添加一次。添加元素时，每次从头遍历给定列表，分别选择该元素或不选择该元素。搜索所有组合。

知识点：res.append(alist[:])：往结果列表res中添加列表alist。需使用alist[:]，否则回溯时pop撤销选择时，列表alist中会删除最后一个元素，结果列表res中也会删除该元素，最终结果则为空列表。

              alist.pop()：删除列表alist中最后一个元素。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def traceback(index):# 终止条件：列表遍历结束if index == n:res.append(alist[:])        # 结果列表中保存组合return# 全排列（每个元素都有，只是顺序不同），每次从头遍历for i in range(0, n):# 每个元素在组合中只能出现一次if nums[i] not in alist:# 选择当前元素alist.append(nums[i])traceback(index + 1)     # 递归，往下继续添加元素# 撤销选择（即不选择当前元素）alist.pop()res = []            # 结果列表，存放所有全排列的组合alist = []          # 一个全排列的组合index = 0           # 在组合中添加到哪个元素n = len(nums)       # 列表长度traceback(index)    # 执行函数return res

3、（难度：困难）【力扣】51. N 皇后

（3-1）使用集合

解题思路：皇后所在位置不能同一行、同一列、不能在两个斜线位置（左上到右下，右上到左下）。因此，三个集合：存放皇后所在列号，两个斜线（左上到右下，行号和列号的差相同。右上到左下，行号和列号的和相同）。搜索每一行皇后所在位置，尝试所有可能结果。

知识点： [ ]：空列表。列表：元素可重复的有序、可变的序列。

               列表.append(元素)：往列表添加元素。

               列表[下标]：获取或修改列表下标对应的元素。

               "间隔符".join(列表)：列表中所有元素按照指定间隔符组合成字符串。间隔符可以为空。

               [元素] * n：列表，列表中有n个相同的指定元素。

               set( )：空集合。集合：元素不重复的无序、可变的序列。

               集合.add(元素)：往集合添加元素。

               集合.remove(元素)：从集合删除元素。

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def trackback(rowindex):# 终止条件：棋盘所有行遍历结束if rowindex == n:board = []                          # 棋盘列表，存放整个棋盘内容for i in range(n):row[queen[i]] = "Q"             # 各行皇后所在的列下标对应元素为Qboard.append("".join(row))      # 各行加入棋盘row[queen[i]] = "."             # 恢复行初始值res.append(board)                   # 结果列表记录最终整个棋盘return# 遍历棋盘所有列for colindex in range(n):# 判断：不与皇后同一列、斜线（左上到右下，行号与列号的差相同。右上到左下，行号与列号的和相同）if colindex not in columns \and colindex - rowindex not in diagonal_1 \and colindex + rowindex not in diagonal_2:# 选择该位置为皇后queen[rowindex] = colindexcolumns.add(colindex)diagonal_1.add(colindex - rowindex)diagonal_2.add(colindex + rowindex)trackback(rowindex + 1)            # 递归搜索# 撤销选择（即该位置不为皇后）columns.remove(colindex)diagonal_1.remove(colindex - rowindex)diagonal_2.remove(colindex + rowindex)res = []                # 结果列表，存放所有最终棋盘结果columns = set()         # 集合，存放所有皇后所在的列下标diagonal_1 = set()      # 集合，存放所有皇后的斜线（左上到右下）diagonal_2 = set()      # 集合，存放所有皇后的斜线（右上到左下）queen = [-1] * n        # 皇后列表，皇后初始值，存放每行皇后所在的列下标row = ['.'] * n         # 行列表，行初始值rowindex = 0            # 目前在哪一行trackback(rowindex)     # 执行函数return res

（3-2）使用二进制

解题思路：将棋盘每行视为一串二进制，尝试所有可能的位置。第一行从最右边（低位）开始搜索，获取皇后所在位置在棋盘上该行的列下标。下一行，新皇后不能同一列，不能斜线（即可能位置为左侧斜线右移一位，右侧斜线左移一位），继续搜索，搜索所有行的皇后位置。再新一轮搜索第一行下一个可能位置，依次类推，深度优先搜索，搜索所有可能结果。

知识点：1 << n：1左移n位。若n=4，则二进制10000。

             （1 << n）-1：若n=4，则结果为二进制1111。即棋盘中一行4位均为可能位置。

             （~(columns | diagonal_1 | diagonal_2）：“|”即or，“~”为取反。即不与已有皇后同一列、两个斜线位置。

              may_pos & (-may_pos) ： 获取二进制may_pos中最右边为1的位置，即皇后可能位置。

              may_pos & (may_pos - 1) ：将二进制may_pos最右边的1置为0，即剩余可能位置。

              bin(...).count("1")：统计二进制中1的个数。以次获取列下标。

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def trackback(rowindex, columns, diagonal_1, diagonal_2):# 终止条件：遍历棋盘所有行if rowindex == n:board = []                      # 保存整个棋盘内容for i in range(n):row[queen[i]] = "Q"         # 皇后所在位置元素为Qboard.append("".join(row))  # 保存各行row[queen[i]] = "."         # 行恢复初始值res.append(board)               # 结果列表中保存最终整个棋盘return# 所有可能的位置may_pos = ((1 << n) - 1) & (~(columns | diagonal_1 | diagonal_2))# 遍历所有可能的位置while may_pos:pos = may_pos & (-may_pos)            # 获取最右边为1的位置colindex = bin(pos - 1).count("1")    # 最右边1的位置转为在棋盘中的列下标queen[rowindex] = colindex            # 保存该行皇后的列下标may_pos = may_pos & (may_pos - 1)     # 将最右边的1置为0，剩余可能位置# 递归搜索trackback(rowindex + 1, columns | pos, (diagonal_1 | pos) << 1, (diagonal_2 | pos) >> 1)res = []                # 结果列表，保存所有的最终棋盘queen = [-1] * n        # 存放各行皇后所在的列下标row = ["."] * n         # 行初始值# 目前所在行号、列号、两个斜线位置rowindex, columns, diagonal_1, diagonal_2 = 0, 0, 0, 0trackback(rowindex, columns, diagonal_1, diagonal_2)return res