罗罗编程学习记录
本页内容 展开查看

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 状态并说明记忆化失效场景
  • [ ] 能把后序递归改成显式栈迭代并对照帧信息
  • [ ] 能区分同值重复与顺序重复,选对去重手段
  • [ ] 每题能报出时间、空间口径,并列边界用例