回溯
本章目标：掌握组合、排列、子集三大回溯模板，能解决 N 皇后、数独等经典搜索问题。
你将学到
- 回溯的本质：DFS + 撤销选择
- 组合问题模板
- 排列问题模板
- 子集问题模板
- 剪枝优化
- N 皇后与数独
1. 概念
回溯法是一种系统搜索所有可能解的方法，本质是深度优先搜索（DFS）加上撤销操作。它的核心框架：
选择一个路径 → 递归 → 撤销选择（回溯）回溯法的通用模板：
python
def backtrack(路径, 选择列表):
if 满足结束条件:
结果.append(路径[:]) # 注意拷贝
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择回溯法的时间复杂度通常是指数级 O(2ⁿ) 或 O(n!)，但它通过剪枝大幅减少实际搜索量。理解回溯的关键是画出决策树——每个节点代表一个状态，每条边代表一个选择。
2. 核心模板
组合问题（LeetCode 77）
python
def combine(n, k):
"""从 1..n 中选 k 个数的所有组合"""
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result排列问题（LeetCode 46）
python
def permute(nums):
"""全排列"""
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result子集问题（LeetCode 78）
python
def subsets(nums):
"""所有子集"""
result = []
def backtrack(start, path):
result.append(path[:]) # 每个节点都是一个子集
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result复杂度
- 组合 C(n,k)：时间 O(C(n,k) * k)
- 排列：时间 O(n! * n)
- 子集：时间 O(2ⁿ * n)
3. 经典题目精讲
LeetCode 39 · 组合总和
题意：给定无重复正整数数组和目标值，找所有和等于目标的组合（元素可重复使用）。
思路：回溯，因为可重复使用，递归时 start 传 i 而非 i+1。剪枝：排序后，当前和 + 候选 > target 则跳过。
python
def combinationSum(candidates, target):
candidates.sort() # 排序便于剪枝
result = []
def backtrack(start, target, path):
if target == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > target:
break # 剪枝
path.append(candidates[i])
backtrack(i, target - candidates[i], path) # i 不是 i+1，可重复
path.pop()
backtrack(0, target, [])
return resultLeetCode 51 · N 皇后
题意：在 N×N 棋盘上放 N 个皇后，使其互不攻击。
思路：逐行放置，每行选一个合法位置，用集合记录已占用的列和对角线。
python
def solveNQueens(n):
result = []
cols = set()
diag1 = set() # 主对角线 row - col
diag2 = set() # 副对角线 row + col
def backtrack(row, board):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# 做选择
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
board[row][col] = 'Q'
backtrack(row + 1, board)
# 撤销选择
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board[row][col] = '.'
backtrack(0, [['.'] * n for _ in range(n)])
return resultLeetCode 79 · 单词搜索
题意：在二维字符网格中搜索单词。
思路：DFS + 回溯，访问过的格子临时标记。
python
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
return False
temp, board[r][c] = board[r][c], '#'
found = (dfs(r+1, c, idx+1) or dfs(r-1, c, idx+1) or
dfs(r, c+1, idx+1) or dfs(r, c-1, idx+1))
board[r][c] = temp # 撤销
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False4. 易错点
- ⚠️ 添加结果时一定要拷贝
path[:]，否则后续修改会影响已存结果 - ⚠️ 排列问题需要
used数组，组合问题用start控制起始位置 - ⚠️ 剪枝前必须排序，否则无法提前终止
- ⚠️ 回溯的撤销操作必须和做选择严格对称
5. 推荐刷题清单
| 题号 | 题名 | 难度 | 关键 |
|---|---|---|---|
| 39 | 组合总和 | Medium | 可重复组合 |
| 46 | 全排列 | Medium | 排列模板 |
| 51 | N 皇后 | Hard | 经典回溯 |
| 77 | 组合 | Medium | 组合模板 |
| 79 | 单词搜索 | Medium | DFS+回溯 |
| 131 | 分割回文串 | Medium | 分割回溯 |
延伸阅读
- LeetCode 官方
- 代码随想录
- 《算法导论》(CLRS)