算法概念速查
什么是回溯算法？选择、递归、撤销三步框架讲透
一句话定义
回溯是在「决策树」上做深度优先搜索的枚举框架：每一层从候选集合里做一个选择、递归进入下一层；递归返回时撤销刚才的选择，回到干净的现场再试下一个分支。三步循环——做选择、递归、撤销选择——配合剪枝砍掉注定无解的分支，就能系统地枚举出排列、组合、子集、棋盘摆放等所有候选方案。
先打个比方
像拿粉笔走迷宫：每到岔路口挑一条没走过的路，走之前画个记号；走到死胡同就退回上一个路口，把记号擦掉，换下一条路。擦记号这一步就是「撤销选择」——不擦，下条路会误以为这里已经走过，整个探索就乱了。
它是怎么运作的
回溯的代码骨架只有五行：终止条件（path 攒够了就收录一份拷贝）→ for 遍历当前候选 → 做选择（path.push、标记 used）→ 递归下一层 → 撤销选择（path.pop、复位 used）。所有排列组合子集题都是往这个骨架里填「候选是什么、何时终止」。
排列和组合的框架差异要刻在脑子里：排列讲顺序，每层都从头扫、用 used 数组挡住已选的数；组合不讲顺序，用 start 参数只往后选，天然避免 [1,2] 和 [2,1] 重复。用 start 去做排列、或用 used 去做组合，都是新手经典翻车。
剪枝是回溯从「能做」到「做得快」的关键：可行性剪枝（剩余的数注定凑不够就提前 return）和同层去重（排序后跳过与前一个相同的候选）是两把最常用的剪刀。
什么时候用：识别信号
题目里出现下面任何一条，就该想到「回溯」。
- 题目要「所有」方案的列表：全排列、所有子集、所有组合、所有切割方式
- 每一步都是「从候选里挑一个」，且这一步会缩小后续的候选范围
- 棋盘 / 网格上的摆放与搜索：N 皇后、单词搜索
- 答案个数天然是指数级（2ⁿ、n!），多项式算法不存在
别和它们搞混
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
为什么收录答案要存 path 的拷贝而不是 path 本身？
path 是同一个引用，后面还会被 push/pop 反复修改；直接 res.append(path) 收进去的是「会继续变化的活对象」，最后结果里所有方案会变成同一个（甚至全空）。必须 res.append(path[:]) 存快照。
忘记撤销选择会出什么症状？
path 越堆越长、used 一直占着，第一条分支之后的所有分支都在被污染的现场上枚举——典型表现是结果数量远少于预期、或方案里混进不该有的元素。递归调用后紧跟一行撤销，成对写。
剪枝从哪下手？
两个方向：一是可行性——当前路径已注定不可能满足条件（剩余数字之和不够、皇后已互相攻击）就立刻返回；二是去重——排序后同一层跳过与前一个相同的候选，避免产出重复方案。