回溯算法：
- 回溯算法是一种算法思想。
- 采用“深度优先搜索（dfs，depth first search）”。
- 采用“尝试”和“回溯”的策略。尝试搜索所有可能的解决方案，遇到不满足条件的撤销选择、回退到回溯点（满足回溯条件的某个状态的点）、尝试其他方法。
- 基本思想：从一条路往前走，能进则进，不能进则退回来，换条路再试。
- 类似穷举法，但有剪枝的功能。剪枝：去除不满足约束条件的尝试、提高效率。
- 通常用递归实现。（也可以用迭代实现，但设计复杂）
回溯算法的伪代码模板：
res = [] # 记录所有的最终解
def traceback(各参数):
if 终止条件：
res.append(最终解) # 保存结果
return
for 方案 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 res3、（难度：困难）【力扣】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" # 各行皇后所在的列下标对应元素为Q
board.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] = colindex
columns.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" # 皇后所在位置元素为Q
board.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, 0
trackback(rowindex, columns, diagonal_1, diagonal_2)
return res
