30 秒速览
- 什么时候用：求所有方案、排列组合、子集、棋盘问题
- 核心思想：带撤销操作的 DFS，遍历决策树
- 时间复杂度：通常 O(n!) 或 O(2^n)
- 空间复杂度：O(n)（递归深度）
一、直觉建立
走迷宫
想象你在走迷宫，遇到岔路口：
- 选择一条路走下去
- 走到死胡同 → 退回岔路口（回溯）
- 尝试另一条路
- 重复直到找到出口
回溯的本质：系统地尝试所有可能，不行就回退。
回溯 vs 递归
- 递归：是一种编程技巧（函数调用自己）
- 回溯：是一种算法思想（尝试 → 失败 → 撤销 → 重试）
回溯通常用递归实现。
决策树
回溯问题都可以抽象成决策树：
求 [1,2,3] 的所有排列：
开始
/ | \
1 2 3 第 1 层：选谁放第一位
/\ /\ /\
2 3 1 3 1 2 第 2 层：选谁放第二位
| | | | | |
3 2 3 1 2 1 第 3 层：只剩一个选择
结果：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
二、回溯模板
def backtrack(路径, 选择列表):
if 满足结束条件:
result.append(路径.copy()) # 注意拷贝
return
for 选择 in 选择列表:
# 做选择
路径.append(选择)
# 递归
backtrack(路径, 新的选择列表)
# 撤销选择（回溯）
路径.pop()
核心三要素：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层
三、典型例题
例题 1：LC 46. 全排列
题目：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
代码
def permute(nums: list[int]) -> list[list[int]]:
result = []
path = []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums):
result.append(path[:]) # 拷贝
return
for i in range(len(nums)):
if used[i]:
continue
# 做选择
path.append(nums[i])
used[i] = True
# 递归
backtrack()
# 撤销选择
path.pop()
used[i] = False
backtrack()
return result
复杂度：时间 O(n × n!)，空间 O(n)
例题 2：LC 78. 子集
题目：给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
示例：
输入：nums = [1,2,3]
输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
思路
子集问题不需要等到最后才收集结果，每个节点都是一个子集。
代码
def subsets(nums: list[int]) -> list[list[int]]:
result = []
path = []
def backtrack(start):
# 每个节点都是一个子集
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1) # 从下一个位置开始，避免重复
path.pop()
backtrack(0)
return result
复杂度：时间 O(n × 2^n)，空间 O(n)
例题 3：LC 77. 组合
题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
示例：
输入：n = 4, k = 2
输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
代码
def combine(n: int, k: int) -> list[list[int]]:
result = []
path = []
def backtrack(start):
if len(path) == k:
result.append(path[:])
return
# 剪枝：还需要 k - len(path) 个，所以 i 最多到 n - (k - len(path)) + 1
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1)
path.pop()
backtrack(1)
return result
剪枝优化：
如果还需要 3 个数，当前从 4 开始，只剩 [4,5]，不够 3 个，可以剪掉
剪枝公式：i <= n - (k - len(path)) + 1
复杂度：时间 O(C(n,k) × k)，空间 O(k)
例题 4：LC 39. 组合总和
题目：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。candidates 中的同一个数字可以无限制重复被选取。
示例：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
代码
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
# 可重复选择，所以还是从 i 开始
backtrack(i, remaining - candidates[i])
path.pop()
backtrack(0, target)
return result
复杂度：时间 O(n^(target/min))，空间 O(target/min)
例题 5：LC 40. 组合总和 II
题目：每个数字只能用一次，candidates 可能有重复元素。
示例：
输入：candidates = [10,1,2,7,6,1,5], target = 8
输出：[[1,1,6],[1,2,5],[1,7],[2,6]]
思路
关键是去重：同一层不能选重复的数。
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
candidates.sort() # 排序，方便去重
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
# 去重：同一层，跳过重复元素
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, remaining - candidates[i]) # 每个数只能用一次
path.pop()
backtrack(0, target)
return result
复杂度：时间 O(2^n)，空间 O(n)
例题 6：LC 79. 单词搜索
题目：给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。
思路
DFS + 回溯，标记已访问的格子。
def exist(board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(i, j, k):
if k == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
# 标记已访问
temp = board[i][j]
board[i][j] = '#'
# 四个方向搜索
found = (dfs(i+1, j, k+1) or
dfs(i-1, j, k+1) or
dfs(i, j+1, k+1) or
dfs(i, j-1, k+1))
# 恢复
board[i][j] = temp
return found
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
复杂度：时间 O(mn × 4^L)，L 是单词长度
例题 7：LC 51. N 皇后（Hard）
题目：在 n×n 的棋盘上放置 n 个皇后，使其不能互相攻击。
思路
按行放置皇后，检查列和对角线是否冲突。
def solveNQueens(n: int) -> list[list[str]]:
result = []
board = ['.' * n for _ in range(n)]
def isValid(row, col):
# 检查列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append(board[:])
return
for col in range(n):
if isValid(row, col):
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
backtrack(row + 1)
board[row] = board[row][:col] + '.' + board[row][col+1:]
backtrack(0)
return result
复杂度：时间 O(n!)，空间 O(n)
四、回溯问题分类
| 问题类型 | 特点 | 遍历起点 |
|---|---|---|
| 排列 | 顺序有关 | 每次从 0 开始，用 used 去重 |
| 组合 | 顺序无关 | 从 start 开始，保证不回头 |
| 子集 | 收集所有节点 | 从 start 开始 |
| 棋盘 | 二维约束 | 按行/列遍历 |
去重策略
- 排列去重：used 数组标记已使用
- 组合/子集去重：
- 排序
if i > start and nums[i] == nums[i-1]: continue
五、常见错误与陷阱
错误 1：忘记拷贝路径
# 错误：直接 append，后续修改会影响
result.append(path)
# 正确：拷贝
result.append(path[:])
错误 2：去重逻辑错误
# 组合去重：i > start
if i > start and nums[i] == nums[i-1]:
continue
# 不是 i > 0！因为 i > 0 会把不同层级的相同元素也跳过
错误 3：忘记撤销选择
# 做选择
path.append(x)
backtrack(...)
# 忘记撤销 ← 导致路径不正确
六、复盘清单
触发信号
- 求所有方案
- 排列/组合/子集
- 棋盘问题（N皇后、数独）
- 需要尝试所有可能
三要素检查
- 路径定义清晰
- 选择列表正确
- 结束条件正确
- 撤销选择
剪枝优化
- 提前终止不满足条件的分支
- 排序后去重
七、题目清单
基础题
| 题号 | 题目 | 难度 | 类型 |
|---|---|---|---|
| 46 | 全排列 | Medium | 排列 |
| 78 | 子集 | Medium | 子集 |
| 77 | 组合 | Medium | 组合 |
| 39 | 组合总和 | Medium | 组合 |
| 40 | 组合总和 II | Medium | 组合去重 |
进阶题
| 题号 | 题目 | 难度 | 类型 |
|---|---|---|---|
| 47 | 全排列 II | Medium | 排列去重 |
| 90 | 子集 II | Medium | 子集去重 |
| 79 | 单词搜索 | Medium | 二维回溯 |
| 51 | N 皇后 | Hard | 棋盘 |
| 37 | 解数独 | Hard | 棋盘 |
| 131 | 分割回文串 | Medium | 字符串分割 |