Backtracking Template

2023-09-02

回溯

回溯 = 决策树上的 DFS：选 → 递归 → 撤销。所有”列出所有可能”的题都是同一个模板，区别只在”选择列表”怎么造。

直觉

想象你在迷宫的每个岔路口都做一件事：放一块小石头记录”我从这条路来”，然后走下去；走到死路或拿到答案就原路退回，把石头捡起来。捡石头这一步就是”回溯”——它让你把同一条 path 列表反复利用，而不是每层都复制一份状态。

所以回溯只有三个动作：

做选择：path.append(c)
递归：进入下一层
撤销：path.pop()

第三步对称于第一步。少一个，状态就脏；多一个，结果就错。

决策树才是本体

排列、组合、子集、分割、N 皇后、数独——它们看起来差别很大，但画出”决策树”以后会发现：回溯永远是在一棵树上做 DFS，只是树的形状不同。

子集：每层决定”选/不选当前元素”，所有节点都是答案，叶子也行内部节点也行
排列：每层从”剩下没用过的”里选一个，只收集叶子，需要 used[]
组合：每层从 start 往后选，避免重复，只收集叶子，需要 start

点 [下一步] 看 path 怎么随着 DFS 推进而变化：选 1 → path=[1]，再选 2 → path=[1,2]，到底了 → 拷贝快照入 ans，然后 pop 回到 [1]，继续走兄弟节点。第二段动画把排列和组合的决策树并排放，能直观看到：排列每个内部节点都向”剩余全部”分叉，组合只向”后面的元素”分叉，所以一棵又胖又满，一棵窄而瘦。

模板

锁死这一段，所有变种都是改”choices”和”结束条件”：

def backtrack(path, choices):
    if 结束条件:
        ans.append(path[:])     # ← 必须拷贝快照，不然全是同一个引用
        return
    for c in choices:
        if not_valid(c):
            continue            # ← 剪枝（去重 / used / 合法性）
        path.append(c)          # 选
        backtrack(path, next_choices(c))
        path.pop()              # 撤销（与 append 对称）

三对必须对称的操作：

path.append ↔ path.pop
used[i] = True ↔ used[i] = False
任何”标脏”的状态修改 ↔ 还原

三大问题族

问题	choices	收集时机
子集 Subsets	`range(start, n)`	每个节点都收
排列 Permutations	全部 + `used[]` 过滤	叶子（`len==n`）
组合 Combinations	`range(start, n)`	叶子（`len==k`）

速记口诀：子集收所有节点，排列叶子配 used，组合叶子配 start。

去重套路

有重复元素时，先排序，同一层跳过重复值：

nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i-1]:
        continue          # 同一层去重：兄弟相同跳过
    ...

为什么是 i > start 而不是 i > 0？因为我们要的是兄弟去重，不是父子去重——i == start 是这一层的第一个选择，再”和上一个相同”那个上一个其实是父节点，不能跳。

经典题

78. 子集 —— 子集模板原题
46. 全排列 —— 排列模板，练 used[]
77. 组合 —— 组合模板，练 start 推进
39. 组合总和 —— 元素可重复用，递归传 i 而不是 i+1
90. 子集 II / 47. 全排列 II —— 练去重的 i > start 模式
51. N 皇后 / 37. 解数独 —— 回溯 + 复杂剪枝，状态恢复成主要难点
131. 分割回文串 —— choices 不是元素而是”切点”，思路同模板

挑题原则：先确认决策树长什么样，再套模板。卡住时手画前两层。

易错点

忘了 path[:] —— ans 里全是同一个引用，回溯完都变空了
append/pop 不对称 —— 漏一个 pop 就开始串味
排列用了 start，或组合用了 used —— 决策树形状就错了
去重前忘排序 —— i > start && nums[i]==nums[i-1] 失效
在递归调用前就 path.append 但在错误位置 pop，把还没递归完的状态污染了

复杂度

时间复杂度 = 决策树节点数 × 每节点工作量。最坏情况由叶子数决定：排列，子集，组合。多出来的那个或来自 path[:] 的拷贝。

一句话总结：回溯不是算法，是”在决策树上 DFS 并恢复现场”这件事的代码化。把树画出来，模板自然就贴上去了。