undo回溯
回溯题型：怎么识别、怎么讲、怎么练
回溯的关键不是“会递归”，而是能有纪律地搜索决策树：当前路径是什么、剩余选择是什么、何时结束、哪里可以剪枝。
覆盖题量
55+
推荐起手
先定义 path 表示什么。
高频误区
忘记撤销状态，导致分支互相污染。
什么时候该想到这个模式
题目要求所有组合、排列、子集或合法构造。
天然存在一个决策树，每层都要做一次选择。
解空间很大，因此剪枝会非常重要。
下手前的检查清单
先定义 path 表示什么。
明确什么叫一组完整解。
写清每一层还剩哪些选择。
每条分支结束后要彻底撤销状态。
真正适合面试表达的解题步骤
1
先把决策树结构建出来。
2
确定当前层候选集怎么生成。
3
递归前先验证选择是否合法。
4
做选择、递归、撤销，三步要一一对应。
5
不可能到达合法解的分支要尽早剪掉。
常见变体
排列搜索
每一层选择一个未使用元素。
组合搜索
通过起始索引避免重复回头选择。
约束回溯
合法性判断和剪枝对性能至关重要。
模板预览
Python公开预览
def backtrack(path):
if complete(path):
answer.append(path[:])
return
for choice in choices(path):
if not valid(choice, path):
continue
path.append(choice)
backtrack(path)
path.pop()
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
入门建立直觉
#39 Combination Sum
找出和为目标值的所有组合，候选数字可重复使用。
因为允许重复使用，所以当前索引可以再次选择；但一旦往后走，就不该再回到更早索引。
入门建立直觉
#46 Permutations
返回数组的所有排列。
每一层递归都在固定排列中的一个位置。
变体补齐关键状态
#78 Subsets
返回数组的所有子集。
每个下标都对应一个二元决策，因此整个答案空间就是一棵深度为 n 的决策树。
变体补齐关键状态
#51 N-Queens
在 n x n 棋盘上放置 n 个皇后，使其互不攻击。
每一行真正需要维护的信息只有哪些列、主对角线和副对角线已被占用。
高频坑点
warning
忘记撤销状态，导致分支互相污染。
warning
保存答案时没复制 path。
warning
索引处理不当，生成重复组合。
warning
没做剪枝，复杂度直接爆炸。
练习顺序建议
1
先做子集和全排列。
2
再刷组合总和和复原 IP 这类题。
3
然后补单词搜索等棋盘题。
4
最后再做 N 皇后这类强剪枝问题。