引言
回溯（Backtracking）本质是带剪枝的 DFS，是面试中最「套模板」的一类题：排列、组合、子集、棋盘类搜索，共享同一套「做选择 → 递归 → 撤销选择」的骨架。刷透回溯题的关键不是背题，而是掌握选择列表的三种构造方式（元素、索引、剩余集合）和去重模板。
本文精选 10 道必刷回溯题，从最简单的子集开始，逐步引入去重、剪枝、棋盘约束，最后汇总一张「题目 → 模板变体」速查表。
前置：/leetcode-greedy-essential-problems/。递归与回溯原理参考 https://plumephp.com/recursion-backtracking/。
目录
- 1. 回溯通用模板
- 2. 子集（LeetCode 78）— 入门骨架
- 3. 全排列（LeetCode 46）— 排列与 used 数组
- 4. 组合（LeetCode 77）— 组合与 startIndex
- 5. 子集 II（LeetCode 90）— 去重模板
- 6. 组合总和（LeetCode 39）— 无限重复
- 7. 括号生成（LeetCode 22）— 剪枝条件
- 8. N 皇后（LeetCode 51）— 棋盘约束
- 9. 单词搜索（LeetCode 79）— 网格 DFS
- 10. 回溯题解速查表
- 延伸阅读
1. 回溯通用模板
def backtrack(path, choices, ...):
# 1. 结束条件：收集答案 / 剪枝
if len(path) == k:
result.append(path[:])
return
# 2. 遍历选择列表
for i, choice in enumerate(choices):
# 2a. 剪枝 / 去重
if used[i]:
continue
# 2b. 做选择
path.append(choice)
used[i] = True
# 2c. 递归下一层
backtrack(path, choices, ...)
# 2d. 撤销选择（回溯的关键）
path.pop()
used[i] = False
三步口诀：选 → 进 → 撤。撤销必须与选择严格对称，否则状态会串层。
2. 子集（LeetCode 78）— 入门骨架
问题：给定不含重复元素的数组，返回所有子集。
思路：对每个元素「选 or 不选」，或按 startIndex 收集每一层的路径。
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) # 下一层从 i+1 开始（不回头）
path.pop()
backtrack(0, [])
return result
要点：子集与组合的区别只在「何时收集答案」——子集收集所有路径，组合只收集长度达标的路径。
3. 全排列（LeetCode 46）— 排列与 used 数组
问题：给定不含重复元素的数组，返回所有排列。
思路：排列中每个位置都可以用任何元素，需要 used 数组记录已选；而子集/组合用 startIndex 避免回头。
def permute(nums):
result = []
n = len(nums)
used = [False] * n
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if used[i]:
continue
path.append(nums[i])
used[i] = True
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
排列 vs 子集 vs 组合：
| 类型 | 约束工具 | 收集时机 |
|---|---|---|
| 子集 | startIndex（不回头） | 每层都收集 |
| 组合 | startIndex（不回头） | 长度 = k 时收集 |
| 全排列 | used 数组（可回头） | 长度 = n 时收集 |
4. 组合（LeetCode 77）— 组合与 startIndex
问题：从 1..n 中选 k 个数的所有组合。
思路：startIndex 保证「下一个元素永远比上一个位置靠后」，天然避免重复组合。
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# 剪枝：剩余可选数必须足够填满 path
# 最多还能取到 n - (k - len(path)) + 1
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
剪枝技巧：for i in range(start, n - (k - len(path)) + 2) —— 当前已选 len(path) 个，还差 k - len(path) 个，i 最多取到 n - 剩余 + 1，否则后面不够数。
5. 子集 II（LeetCode 90）— 去重模板
问题：数组含重复元素，返回所有子集（不重复）。
去重模板：先排序，if i > start and nums[i] == nums[i-1]: continue 跳过同层重复。
def subsets_with_dup(nums):
nums.sort()
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # 同层去重
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
为什么是 i > start 而不是 i > 0：i > start 只去掉同一层里重复选择；i > 0 会误伤「不同层但数值相同」的合法选择（如 [1,1,2] 选第一个 1 再选第二个 1 是合法的）。
6. 组合总和（LeetCode 39）— 无限重复
问题：数组无重复元素，元素可以无限次使用，求所有和为 target 的组合。
思路：因为元素可重复使用，下一层 startIndex 不 +1（可以再选当前元素），但配合 sum 剪枝。
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: # 剪枝：剩余不够
break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i 不 +1，可复用
path.pop()
backtrack(0, [], target)
return result
变体：组合总和 II（LeetCode 40） — 元素只能使用一次 + 有重复 → 排序 +
i > start去重 +i+1递归。
7. 括号生成（LeetCode 22）— 剪枝条件
问题：生成 n 对括号的所有合法组合。
思路：每次可加 ( 或 )，但右括号数绝不能超过左括号数（否则非法）。用两个计数器剪枝。
def generate_parenthesis(n):
result = []
def backtrack(path, left, right):
if len(path) == 2 * n:
result.append(path)
return
if left < n:
backtrack(path + '(', left + 1, right)
if right < left:
backtrack(path + ')', left, right + 1)
backtrack('', 0, 0)
return result
剪枝本质：right < left 保证任意前缀中 ( ≥ )——这正是合法括号串的充要条件。
8. N 皇后（LeetCode 51）— 棋盘约束
问题：n×n 棋盘放 n 个皇后，任意两个不能同行同列同对角线。
思路：每行放一个，用三个集合记录「被占用的列、主对角线、副对角线」。行号由递归深度天然保证不冲突。
def solve_n_queens(n):
result = []
cols, diag1, diag2 = set(), set(), set()
def backtrack(row, board):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
d1, d2 = row - col, row + col
if col in cols or d1 in diag1 or d2 in diag2:
continue
cols.add(col); diag1.add(d1); diag2.add(d2)
board[row][col] = 'Q'
backtrack(row + 1, board)
board[row][col] = '.'
cols.remove(col); diag1.remove(d1); diag2.remove(d2)
backtrack(0, [['.'] * n for _ in range(n)])
return result
对角线技巧：主对角线 row - col 恒定，副对角线 row + col 恒定——这是棋盘类问题的通用技巧。
9. 单词搜索（LeetCode 79）— 网格 DFS
问题：在 m×n 网格中找单词，可上下左右走，每个格子只能用一次。
思路：从每个起点开始 DFS，边走边匹配，用「标记 → 撤销」代替 visited 数组（就地修改）。
def exist(board, word):
m, n = len(board), len(board[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(i, j, k):
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
board[i][j] = '#' # 标记已访问
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and dfs(ni, nj, k + 1):
return True
board[i][j] = word[k] # 撤销标记（回溯）
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
要点：网格 DFS 与普通回溯的区别是选择列表 = 四个方向 + 边界检查；# 标记在失败路径上会被自动撤销。
10. 回溯题解速查表
| 题目 | 模板变体 | 关键技巧 |
|---|---|---|
| 子集 78 | startIndex，全收集 | 每层收集 |
| 子集 II 90 | startIndex + 去重 | i > start 同层去重 |
| 全排列 46 | used 数组 | 可回头 |
| 全排列 II 47 | used + 去重 | 排序 + i>0 and used[i-1] |
| 组合 77 | startIndex + 剪枝 | 剩余数不足剪枝 |
| 组合总和 39 | 可复用 | 递归 i 不 +1 |
| 组合总和 II 40 | 不可复用 + 去重 | 排序 + i > start |
| 括号生成 22 | 双计数剪枝 | right < left |
| N 皇后 51 | 集合判冲突 | 行列对角线 |
| 单词搜索 79 | 网格 DFS | 就地标记 |
一句话总结：先确定「是排列还是组合」（used vs startIndex），再确定「能否重复」和「有无重复元素」（去重模板），最后套骨架。
延伸阅读
- /leetcode-greedy-essential-problems/ — 贪心：另一类「局部决策」题
- https://plumephp.com/recursion-backtracking/ — 回溯原理：递归树、剪枝策略、排列组合子集区分
- https://plumephp.com/graph-theory/ — DFS/BFS 在图论中的系统应用
- LeetCode 回溯标签 — 完整题库
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。