一、全排列（Leetcode 46）
与组合问题不同，排列问题要注意2个特点：
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素
class Solution:
def permute(self, nums):
result = [] # 存储所有的排列
self.backtracking(nums, [], [False] * len(nums), result) # 调用回溯函数开始排列生成
return result # 返回所有排列结果
def backtracking(self, nums, path, used, result):
# 基准条件：当路径长度等于nums长度时，说明已经生成了一个完整排列
if len(path) == len(nums):
result.append(path[:]) # 将当前排列添加到结果中
return
# 遍历每个元素，尝试放入路径中
for i in range(len(nums)):
# 如果nums[i]已经被使用过，跳过该元素
if used[i]:
continue
# 标记当前元素为已使用
used[i] = True
# 将当前元素添加到路径中
path.append(nums[i])
# 递归生成下一个排列
self.backtracking(nums, path, used, result)
# 回溯：撤销当前选择
path.pop() # 从路径中移除当前元素
used[i] = False # 将当前元素标记为未使用，供后续递归使用
二、全排列II （Leetcode 47）
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
class Solution:
def permuteUnique(self, nums):
nums.sort() # 排序，方便去重
result = [] # 存储所有唯一排列
self.backtracking(nums, [], [False] * len(nums), result) # 调用回溯函数
return result # 返回所有排列结果
def backtracking(self, nums, path, used, result):
# 基准条件：路径长度等于nums长度时，说明生成了一个完整排列
if len(path) == len(nums):
result.append(path[:]) # 将当前路径的副本加入结果
return
# 遍历每个元素，尝试加入当前路径
for i in range(len(nums)):
# 如果当前元素与前一个相同，并且前一个元素未被使用，则跳过，避免重复排列
if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:
continue
# 标记当前元素为已使用
used[i] = True
path.append(nums[i]) # 将当前元素加入路径
self.backtracking(nums, path, used, result) # 递归生成下一个排列
path.pop() # 回溯，移除当前元素
used[i] = False # 将当前元素标记为未使用，供后续递归使用
三、重新安排行程（Leetcode 332）
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
self.adj = {} # 用于存储每个城市到其他城市的航班
# 将航班按目的地字母排序
tickets.sort(key=lambda x: x[1])
# 构建每个城市的邻接表
for u, v in tickets:
if u in self.adj:
self.adj[u].append(v)
else:
self.adj[u] = [v]
self.result = [] # 存储结果的路径
self.dfs("JFK") # 从JFK出发
return self.result[::-1] # 结果是反向的，返回反转后的路径
def dfs(self, s):
# 当城市有可用航班时，继续深度优先搜索
while s in self.adj and len(self.adj[s]) > 0:
v = self.adj[s][0] # 选择字母顺序最小的目的地
self.adj[s].pop(0) # 移除已使用的航班
self.dfs(v) # 从新的城市继续深度搜索
self.result.append(s) # 记录当前城市
四、N皇后（Leetcode 51）
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = [] # 存储最终结果的二维字符串数组，存放所有有效解
# 初始化一个棋盘，棋盘是由 n 行字符串组成，每行包含 n 个 '.'，表示空位置
chessboard = ['.' * n for _ in range(n)] # 使用 '.' 表示空格
self.backtracking(n, 0, chessboard, result) # 回溯求解，起始行从0开始
# 将结果中的每行列表转换成字符串并返回
return [[''.join(row) for row in solution] for solution in result]
def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:
# Base case: 如果已经放置了 n 个皇后，说明找到了一种解
if row == n:
result.append(chessboard[:]) # 将当前棋盘布局加入到结果集中
return
# 对当前行的每一列进行尝试
for col in range(n):
# 如果当前位置合法，放置皇后并递归处理下一行
if self.isValid(row, col, chessboard):
# 放置皇后，修改棋盘当前行的列为 'Q'
chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]
# 递归处理下一行
self.backtracking(n, row + 1, chessboard, result)
# 回溯：撤销当前皇后的放置
chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]
def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:
# 检查当前列是否已经有皇后
for i in range(row):
if chessboard[i][col] == 'Q':
return False # 列冲突，返回不合法
# 检查 45 度角方向（左上到右下的对角线）是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == 'Q':
return False # 45度角冲突，返回不合法
i -= 1
j -= 1
# 检查 135 度角方向（右上到左下的对角线）是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == 'Q':
return False # 135度角冲突，返回不合法
i -= 1
j += 1
return True # 没有冲突，当前位置合法