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

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 求最短扩散时间
  • [ ] 每题能报出时间、空间口径,并列边界用例