第14次内容

📚 课前回顾：N皇后问题（回溯算法应用）

同学们好！在开始今天的新内容之前，我们先快速回顾一下上节课学习的重点内容——N皇后问题。

🎯 问题目标

• 在一个 N×N 的国际象棋棋盘上放置 N 个皇后；
• 要求 任意两个皇后都不能互相攻击，也就是说：
  • 不能在同一 行（我们通过逐行放置自然避免）；
  • 不能在同一 列；
  • 不能在同一条 主对角线（从左上到右下）或 副对角线（从右上到左下）。

🧠 核心思想：回溯算法（Backtracking）

• 逐行尝试：我们在每一行中尝试放置一个皇后；
• 可行性检查：通过 checkPosition 函数判断当前列和两条对角线是否安全；
• 递归探索：若当前位置合法，则递归进入下一行；
• 回溯恢复：递归返回后，将当前位置恢复为 '.'，以便尝试其他列。

🔍 关键函数说明

• fillTheBoard(chessBoard, layer, N)：递归函数，负责在第 layer 行尝试放置皇后；
• checkPosition(chessBoard, row, col, N)：检查 (row, col) 位置是否可以安全放置皇后；
  • 检查上方所有行的 同一列；
  • 检查左上方和右上方的 对角线。

💡 输出格式

• 每个合法解以 N×N 字符矩阵形式输出（'Q' 表示皇后，'.' 表示空位）；
• 每个解后跟一条分隔线 -----------------------------；
• 最后输出 总解法数量。

⚠️ 注意事项

• 该实现会输出全部可行解；
• 当 N 较大时（如 N ≥ 10），解的数量急剧增长，程序运行时间较长，实际应用中常需剪枝优化或限制输出数量。

---

通过这个经典问题，我们深入理解了回溯算法的基本框架：尝试 → 验证 → 递归 → 回退。这种“试错+撤销”的思想在许多组合优化问题（如数独、全排列、子集生成等）中都有广泛应用。

问题思考：

• 为什么我们不需要检查“行冲突”？
• 对角线是如何通过行列下标判断的？
• 如果让你优化 checkPosition，你会怎么做？

本次内容

1.电话号的字母组合

2.组合总和

📌 本节课内容总结：回溯法在组合问题中的应用

本节课深入了学习两个典型的回溯算法应用问题：

1. 组合总和（Combination Sum）
   • 给定无重复正整数数组 candidates 和目标值 target，找出所有可重复使用元素的组合，使其和等于 target。
2. 电话号码的字母组合（Letter Combinations）
   • 给定一个由数字 2–9 组成的字符串，返回其对应所有可能的字母组合（按照电话键盘映射）。

---

🔁 一、共同规律：回溯法的通用框架

尽管问题背景不同，但两者都遵循回溯算法的统一模式，核心思想是 “试探 → 递归 → 撤销”：

步骤	说明	组合总和	电话号码
1. 状态表示	用一个中间变量记录当前路径	List<Integer> path	String path
2. 递归函数	构建解的主逻辑	backtrack(target, start, path)	backtrack(index, path)
3. 终止条件	何时得到一个完整解？	target == 0	index == digits.length()
4. 选择列表	当前可选的元素有哪些？	从 start 开始的 candidates[i]	当前数字对应的所有字母
5. 做选择	将元素加入路径	path.add(candidates[i])	path + letter
6. 递归探索	向下一层搜索	backtrack(target - val, i, ...)	backtrack(index + 1, ...)
7. 撤销选择	回溯恢复状态	path.removeLast()	（字符串不可变，天然回溯）

✅ 关键共性：

• 都是穷举所有满足条件的组合；
• 都通过递归深度控制“组合长度”或“目标剩余值”；
• 都利用剪枝/边界判断提前终止无效路径（如 target < 0）。

---

⚠️ 二、注意事项（易错点）

1. 组合总和

• 允许重复使用元素 → 递归时传入的起始索引是 i（不是 i+1）；
• 避免重复组合（如 [2,3] 与 [3,2]）→ 通过 start 参数保证顺序不回头；
• 必须处理 target < 0 的情况，否则会无限递归。

2. 电话号码字母组合

• 输入可能为空 → 需要特判 digits == null || digits.length() == 0，直接返回空列表；
• 字符串不可变性 → 每次递归传入新字符串（如 path + letter），天然实现“撤销”，无需手动 remove；
• 映射表设计 → 使用 phoneMap 数组（索引即数字）提升可读性与效率。

---

💡 三、启发与延伸思考

1. 回溯的本质是“带记忆的 DFS”

• 两个问题都构建了一棵隐式的解空间树：
  • 组合总和：每个节点是“选哪个数”；
  • 电话号码：每个节点是“选哪个字母”。
• 回溯 = 深度优先遍历 + 状态恢复。

2. 可变 vs 不可变数据结构影响实现方式

• 使用 List（可变）需手动 add/remove；
• 使用 String（不可变）通过传参自然回溯，代码更简洁但可能有内存开销。

3. 通用回溯模板（建议掌握）

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径副本);
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 新的选择列表);
        撤销选择;
    }
}

4. 优化方向

• 剪枝：对 candidates 排序后，若 target - candidates[i] < 0 可提前 break；
• 空间优化：用 StringBuilder 替代字符串拼接（电话号码问题）；
• 避免重复解：控制起始索引是关键技巧。

---

🎯 小结

问题	搜索维度	状态变化	是否可重复	关键控制
组合总和	目标值递减	target、path	✅ 元素可重复	start 索引防重复组合
电话号码	字符位置递增	index、path	❌（但每个数字对应多字母）	映射表 + 位置索引

回溯法不是“暴力”，而是有策略的穷举。掌握其框架，就能举一反三，应对大多数组合、排列、分割、子集类问题。