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

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 为主;复杂度标注平均/最坏口径,不确定版本行为标注待确认。