02.6.1 递归与回溯框架
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归
这个知识域解决什么问题
回溯与递归是搜索类题目的底层框架。本知识域围绕一条主线展开:递归三要素与递归树 → 回溯模板与剪枝 → 记忆化与递归转迭代 → 回溯综合与去重。所有题目先讲清决策树结构、现场管理与复杂度口径,再给可运行代码与边界用例。
知识地图
递归三要素与递归树(1)
→ 回溯模板与剪枝(2)
→ 记忆化与递归转迭代(3)
→ 回溯综合与去重(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.6.1.1 | 递归三要素与递归树 | 递归定义、终止条件与收敛、调用栈与栈帧、递归树估复杂度、尾递归、分治、现场传递、递归陷阱 | 20 |
| 02.6.1.2 | 回溯模板与剪枝 | 决策树 DFS、选择/撤销现场、结果拷贝、剪枝安全、顺序剪枝、去重判据、复杂度口径、模板选型 | 20 |
| 02.6.1.3 | 记忆化与递归转迭代 | 重叠子问题、memo 状态设计、自顶向下/自底向上、显式栈模拟帧、后序迭代、递归转迭代代价与对照 | 20 |
| 02.6.1.4 | 回溯综合与去重 | 重复解两类来源、排序相邻跳过、used 同层同支判据、层上哈希、start 方向、子集/排列/组合去重、剪枝去重配合 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握递归思维与复杂度估算,再 2 练熟回溯模板与现场恢复,3 理解记忆化与迭代改造,最后 4 汇总去重与剪枝的系统方法。
自检
- [ ] 能说清递归三要素并画出递归树估算复杂度
- [ ] 能手写通用回溯模板,做选择与撤销成对、结果拷贝
- [ ] 能判断剪枝条件安全,写出顺序剪枝与剩余不足剪枝
- [ ] 能设计 memo 状态并说明记忆化失效场景
- [ ] 能把后序递归改成显式栈迭代并对照帧信息
- [ ] 能区分同值重复与顺序重复,选对去重手段
- [ ] 每题能报出时间、空间口径,并列边界用例