信息技术大学
回溯
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
回溯
数据结构与算法·面试高频 · 第 4 章 算法思想
回溯框架与剪枝
回溯 = 决策树遍历：做选择、递归、撤销选择；剪枝砍掉无效子树是灵魂。
框架
路径加选择列表：选、递归、撤销三步
剪枝
可行性剪枝与同层去重，越早砍越省
复杂度
候选解指数级，剪枝质量决定生死
N 皇后
逐行放皇后：列与两条对角线的占用集合，一个集合一次判断，回溯不慌。
行间不冲突
每行只放一个，行冲突天然不存在
对角标记
row−col 与 row+col 各一个集合判斜线
对称剪枝
首行只试半边，答案数翻倍即可
括号生成
左右括号计数：左没超 n 可加，右少于左可加，规则天然保证合法。
两条规则
左括号数 < n 可放左；右 < 左可放右
合法性
规则本身保证任意前缀合法，无须事后验证
单词搜索
网格找词：每格向四邻走，走过的格子临时改字符当 visited，回溯还原。
起点枚举
从每个匹配首字母的格子出发尝试
原地标记
改字符防回头，返回前改回原字符
剪枝
字符不匹配立刻返回，长度不足提前剪
本节要点
- ✓回溯三步：选、递归、撤销
- ✓N 皇后：三个集合挡列与斜线
- ✓括号生成：计数规则保合法
- ✓单词搜索：原地标记来回还原
延伸主题：手写 N 皇后计数刷电话号码字母组合
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1回溯与 DFS 是什么关系？
参考答案DFS 是图的遍历骨架；回溯是在决策树上的 DFS，多了「撤销选择」——状态要恢复到进子树之前，其他分支才能干净地重走。本质是带状态恢复的 DFS。
2同层去重为什么必须先排序？
参考答案去重靠「同层跳过与前一个相同的值」；不排序时相同值不相邻，比较无从谈起。排序让等值元素聚在一起，一条判断就挡住整批重复分支。
3剪枝的收益为什么远超「解出来再过滤」？
参考答案指数树的成本随深度爆炸：浅层砍掉一个非法分支等于删除整棵子树；事后过滤只省最后的收集，剪枝省的是整段搜索。越早砍越值钱。