回溯决策树
本节目标
用路径、选择和撤销选择，把排列、组合与构造问题统一为可检查的决策树。
回溯不是另一种神秘的递归语法，而是在深度优先搜索一棵“所有可能选择”的树时，明确保存并恢复当前路径。每一层只回答一个问题：当前还能选什么？选了以后，下一层要决定什么？当这一条分支结束，怎样把状态还原给兄弟分支？
识别信号
- 要枚举排列、组合、子集或所有满足约束的构造结果；
- 每次选择会形成一条逐步增长的路径，结果通常是路径的副本；
- 分支之间共享一个可变容器，递归返回后必须撤销刚才的选择；
- 同一元素能否再次选择、后续从哪里选择，会直接决定是否产生重复结果；
- 题目要求构造合法字符串、序列或集合，而不是只求一个最优值。
问题模型与核心不变量
把递归调用看成决策树的一个节点。path 保存从根到当前节点已经做出的选择；循环枚举当前节点的下一步选择；递归返回后删除刚加入的内容，使 path 恢复为进入该循环前的状态。
排列的顺序有意义，后续仍能从全部元素中选择，但同一条路径不能重复用同一个元素，因此用 used[index] 标记“这个下标是否已进入当前路径”。组合和子集的顺序无意义，后续只从 start 及其后方选择，start 同时表达了“前面的元素已经处理过”和“不会重新排列同一组元素”。
答案的收集位置也属于不变量。全排列、固定长度组合和括号生成只有路径达到目标时才在叶子收集；子集的每个节点都代表一个合法选择集，所以进入函数就收集。若允许候选数字重复使用，下一层仍传当前下标；若按输入位置构造字符串，下一层把位置推进一格。
通用模板
排列类在叶子收集答案，并用 used 约束一条路径：
backtrack(path):
if path 达到目标长度:
复制 path 到答案
return
for 每个候选下标:
if used[下标]:
continue
used[下标] = true
path 加入候选
backtrack(path)
path 删除末尾
used[下标] = false
组合与子集类把“还能从哪里选”写为 start：
backtrack(start):
按题意在当前节点收集 path
for index 从 start 到末尾:
path 加入候选[index]
backtrack(下一层的起点)
path 删除末尾
做选择和撤销选择必须成对出现。把撤销放在递归调用后，才能保证下一次循环看到的仍是同一层原本的状态。
模板变体
- 全排列把
used作为路径内的占用标记，下一层仍从全部下标枚举。 - 子集在每个节点收集答案；组合只在路径长度等于
k时收集，并可根据还缺多少个数字缩小循环上界。 - 组合总和先排序。候选值已经超过剩余目标时，后面的候选更大，可以立即停止；允许重复选择时递归继续从当前下标开始。
- 电话号码把递归层数绑定到数字位置，每层只枚举该数字对应的字符集合。
- 括号生成把已用左、右括号数作为状态，只有右括号数小于左括号数时才允许加入右括号。
母题序列
按必学顺序练习：
- 全排列（必学）：用
used画出顺序敏感的完整决策树。 - 子集（必学）：理解每一个搜索节点都可以是答案。
- 组合（必学）：用
start保持下标单调递增并加入剩余数量剪枝。 - 组合总和（必学）：允许重复选择，并用排序后的剩余目标停止无效分支。
- 电话号码的字母组合（必学）：按输入位置推进多分支字符串构造。
- 括号生成（必学）：在生成过程中持续维护前缀合法性。
常见误区
- 把排列题也限制为从
start往后选择，漏掉不同顺序的结果。 - 在递归前修改
path，却没有在返回后删除末尾，导致后续分支携带错误状态。 - 将
path本身而不是副本加入答案，之后回溯会把所有已记录答案一并改掉。 - 子集只在叶子收集，漏掉中间节点代表的合法子集。
- 用集合在最后统一去重，掩盖了决策树边界设计错误；本栏的题都应从选择范围上避免重复。
迁移方向
当“是否可选”不再只由 used 或 start 决定，而要维护局部合法性、多个集合约束或网格访问现场时，下一步学习约束型回溯。当状态不必恢复、目标变成连通性或最短步数时，则转向网格 DFS 或 BFS 的状态图模型。