02.6 回溯与递归
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 递归三要素、终止条件与收敛、调用栈与栈帧、递归树估复杂度、尾递归与分治
- 回溯决策树模板、选择/撤销现场、结果拷贝、剪枝安全与顺序剪枝、复杂度口径
- 重叠子问题与记忆化、自顶向下/自底向上、显式栈模拟递归、递归转迭代
- 子集、组合、组合总和、括号生成、回文分割、复原 IP
- 全排列与去重、下一个排列、第 k 个排列、康托展开、交换法排列
- N 皇后冲突标记与对角线编号、单词搜索、数独求解与候选剪枝、位掩码
- 岛屿数量/面积/周长、被围绕区域、多源 BFS、连通块模板与网格标记策略
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.6.1 | 递归与回溯框架 | 4 个子主题 80 题:递归三要素与递归树、回溯模板与剪枝、记忆化与递归转迭代、回溯综合与去重 |
| 02.6.2 | 经典回溯题型 | 4 个子主题 80 题:组合子集类、排列类、棋盘与 N 皇后数独、岛屿与搜索类 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.6.1.1-008 | 斐波那契递归与重复子问题 | 简单 | ★★★★☆ | 递归三要素与递归树 |
| 02.6.1.1-010 | 链表反转递归 | 中等 | ★★★★☆ | 递归三要素与递归树 |
| 02.6.1.2-002 | 通用回溯模板 | 中等 | ★★★★★ | 回溯模板与剪枝 |
| 02.6.1.2-007 | 排序后顺序剪枝 | 中等 | ★★★★☆ | 回溯模板与剪枝 |
| 02.6.1.2-009 | 重复元素同层去重 | 中等 | ★★★★☆ | 回溯模板与剪枝 |
| 02.6.1.3-002 | 记忆化搜索实现 | 中等 | ★★★★☆ | 记忆化与递归转迭代 |
| 02.6.1.3-008 | 显式栈模拟递归帧 | 困难 | ★★★☆☆ | 记忆化与递归转迭代 |
| 02.6.1.4-003 | used[i-1] 区分同层同支 | 困难 | ★★★★☆ | 回溯综合与去重 |
| 02.6.2.1-001 | 子集 I(LC 78) | 中等 | ★★★★★ | 组合子集类 |
| 02.6.2.1-002 | 子集 II 去重(LC 90) | 中等 | ★★★★☆ | 组合子集类 |
| 02.6.2.1-003 | 组合总和(LC 39) | 中等 | ★★★★★ | 组合子集类 |
| 02.6.2.1-004 | 组合总和 II(LC 40) | 中等 | ★★★★☆ | 组合子集类 |
| 02.6.2.1-012 | 括号生成(LC 22) | 中等 | ★★★★★ | 组合子集类 |
| 02.6.2.1-013 | 分割回文串(LC 131) | 中等 | ★★★★☆ | 组合子集类 |
| 02.6.2.2-001 | 全排列 I(LC 46) | 中等 | ★★★★★ | 排列类 |
| 02.6.2.2-002 | 全排列 II 去重(LC 47) | 中等 | ★★★★☆ | 排列类 |
| 02.6.2.2-003 | 下一个排列(LC 31) | 中等 | ★★★★☆ | 排列类 |
| 02.6.2.2-007 | 第 k 个排列(LC 60) | 困难 | ★★★☆☆ | 排列类 |
| 02.6.2.3-001 | N 皇后(LC 51) | 困难 | ★★★★☆ | 棋盘与 N 皇后数独 |
| 02.6.2.3-005 | 单词搜索(LC 79) | 中等 | ★★★★★ | 棋盘与 N 皇后数独 |
| 02.6.2.3-007 | 解数独(LC 37) | 困难 | ★★★☆☆ | 棋盘与 N 皇后数独 |
| 02.6.2.3-014 | 单词搜索 II(LC 212) | 困难 | ★★★☆☆ | 棋盘与 N 皇后数独 |
| 02.6.2.4-001 | 岛屿数量(LC 200) | 中等 | ★★★★★ | 岛屿与搜索类 |
| 02.6.2.4-002 | 岛屿最大面积(LC 695) | 中等 | ★★★★☆ | 岛屿与搜索类 |
| 02.6.2.4-003 | 被围绕的区域(LC 130) | 中等 | ★★★★☆ | 岛屿与搜索类 |
| 02.6.2.4-004 | 腐烂橘子多源 BFS(LC 994) | 中等 | ★★★★☆ | 岛屿与搜索类 |
当前状态
- 02.6.1 已完成 4 个子主题、80 题;02.6.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;复杂度标注平均/最坏口径,不确定版本行为标注待确认。