02.6.2 经典回溯题型
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归
这个知识域解决什么问题
在框架之上落地高频回溯题型。本知识域按题型分四块:组合子集类 → 排列类 → 棋盘与 N 皇后数独 → 岛屿与搜索类;每类给出状态组织、剪枝去重、复杂度口径与典型原题概要。
知识地图
组合子集类(1)
→ 排列类(2)
→ 棋盘与 N 皇后数独(3)
→ 岛屿与搜索类(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.6.2.1 | 组合子集类 | 子集 I/II、组合总和 I~IV、C(n,k)、电话号码、复原 IP、括号生成、回文分割、组合剪枝与复杂度 | 20 |
| 02.6.2.2 | 排列类 | 全排列 I/II、下一个排列、字典序、第 k 个排列康托、可重排列、交换法、排列去重与复杂度 | 20 |
| 02.6.2.3 | 棋盘与 N 皇后数独 | N 皇后冲突标记、对角线编号、单词搜索、数独求解与候选剪枝、位掩码、棋盘搜索顺序 | 20 |
| 02.6.2.4 | 岛屿与搜索类 | 岛屿数量/面积/周长、包围区域、多源 BFS、填海造陆、连通块模板、网格越界与标记策略 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,LeetCode 只写编号与题意概要。
学习路径
先 1 掌握组合子集的 start 与收集时机,再 2 对比排列的 used 与顺序语义,3 攻克棋盘约束回溯,最后 4 区分洪水填充与回溯型网格搜索。
自检
- [ ] 能写子集、组合、组合总和各变体并区分可否重复选取
- [ ] 能写全排列与去重排列,讲清 used 同层同支判据
- [ ] 能用康托定位第 k 个排列
- [ ] 能实现 N 皇后三类冲突标记与数独回溯剪枝
- [ ] 能区分网格 DFS 永久标记与回溯撤销
- [ ] 能手写多源 BFS 求最短扩散时间
- [ ] 每题能报出时间、空间口径,并列边界用例