第15次内容

📚 课前回顾：回溯法与分支限界（上节课重点）

同学们，上节课我们深入学习了回溯法（Backtracking）这一重要的算法思想，并通过两个经典问题进行了实践：

1️⃣ 电话号码的字母组合

• 问题核心：给定一个由数字 2-9 组成的字符串，返回其在电话按键上对应的所有字母组合。
• 解法要点：
  • 使用递归 + 回溯构建所有可能的组合。
  • 每一步选择当前数字对应的一个字母，加入路径（path）；
  • 当路径长度等于输入数字串长度时，得到一个完整解，加入结果集；
  • 递归返回后撤销选择（回溯），尝试下一个字母。
• 关键思想：

  构建一棵解空间树，通过深度优先搜索（DFS）遍历所有可能路径。

2️⃣ 组合总和（Combination Sum）

• 问题核心：从候选数组中选出若干数字（可重复使用），使其和等于目标值 target。
• 解法要点：
  • 同样采用回溯法，但需注意允许重复选取同一元素；
  • 通过设置起始索引 start 避免产生重复组合（如 [2,3] 和 [3,2] 视为相同）；
  • 递归时传入 i（而非 i+1）实现元素复用；
  • 剪枝条件：若当前和已超过 target（即 target < 0），立即返回。
• 关键思想：

  在搜索过程中控制选择范围 + 有效剪枝，提升效率。

---

🔍 回顾总结

• 回溯法 = 递归 + 选择 + 撤销选择
• 它适用于组合、排列、子集、路径枚举等需要穷举解空间的问题；
• 虽然最坏时间复杂度较高（通常是指数级），但通过合理的剪枝可以大幅减少无效搜索；
• 与分支限界法不同，回溯法通常采用深度优先搜索，而分支限界常使用广度优先或优先队列（下节课将进一步对比）。

---

本次内容

1.装载问题