216. 组合总和 III 回溯

目录

问题描述

解决思路

关键点

代码实现

代码解析

1. 初始化结果和路径

2. 深度优先搜索（DFS）

3. 遍历候选数字

4. 递归与回溯

示例分析

复杂度与优化

回溯算法三部曲

1. 路径选择：记录当前路径

2. 递归探索：进入下一层决策

3. 撤销选择：回溯到上一层

 代码框架模板

关键点解析

总结

---

问题描述

我们需要找出所有由 k 个不同数字组成的组合，这些数字的范围是 1 到 9，且它们的和等于 n。组合中的数字不能重复使用，且结果不能包含重复的组合。例如，当 k=3, n=7 时，唯一有效的组合是 [1,2,4]。

解决思路

这个问题可以通过回溯算法解决。核心思想是递归地尝试每一个可能的数字，逐步构建符合条件的组合，并通过剪枝优化减少无效搜索。

关键点

1. 数字范围固定：所有数字只能在 1-9 中选择。

2. 组合唯一性：每个组合中的数字必须严格递增，避免重复（如 [1,2,4] 和 [2,1,4] 被视为同一组合）。

3. 剪枝优化：在递归过程中，提前终止不可能满足条件的分支，大幅提高效率。

代码实现

var combinationSum3 = function (k, n) {const result = [];const path = [];const dfs = (start, sum) => {// 终止条件：路径长度等于k且和等于nif (path.length === k && sum === n) {result.push([...path]);return;}// 遍历候选数字for (let i = start; i <= 9; i++) {// 剪枝1：剩余数字不够组成k个数if (path.length + (9 - i + 1) < k) break; // 剪枝2：当前和超过nif (sum + i > n) break; path.push(i);dfs(i + 1, sum + i); // 递归下一层，起始位置为i+1path.pop();          // 回溯，撤销选择}};dfs(1, 0); // 从数字1开始，初始和为0return result;
};

代码解析

1. 初始化结果和路径

• result：存储所有符合条件的组合。

• path：记录当前递归路径中的数字。

2. 深度优先搜索（DFS）

• 参数：start 表示当前递归的起始数字，sum 表示路径中数字的当前和。

• 终止条件：当路径长度等于 k 且和等于 n 时，将当前路径加入结果列表。

3. 遍历候选数字

• 循环范围：从 start 到 9，确保数字递增，避免重复组合。

• 剪枝1：path.length + (9 - i + 1) < k
  如果当前已选数字数量加上剩余可用数字数量不足 k，说明无法组成有效组合，直接终止循环。
  例如：k=3，当前已选1个数字，剩余可用数字是 8 和 9（共2个），显然不够选2个。

• 剪枝2：sum + i > n
  如果当前路径和加上 i 已经超过 n，后续更大的数字只会让和更大，无需继续搜索。

4. 递归与回溯

• 选择数字：将 i 加入路径，递归调用 dfs 处理下一个数字。

• 撤销选择：递归返回后，将 i 从路径中移除，尝试其他可能的数字。

示例分析

以 k=3, n=7 为例：

1. 初始调用：dfs(1, 0)。

2. 第一层循环：i=1，路径为 [1]，和为1。

3. 第二层循环：i=2（起始为2），路径为 [1,2]，和为3。

4. 第三层循环：i=4（起始为3），路径为 [1,2,4]，和为7，满足条件，加入结果。

5. 回溯：递归返回，尝试其他数字，但均无法满足条件，最终结果唯一。

---

复杂度与优化

• 时间复杂度：最坏情况为 O(9! / (k!(9-k)!))，即组合数的时间。

• 空间复杂度：递归栈深度为 k，空间复杂度为 O(k)。

通过剪枝，实际运行时间远低于理论最坏情况，因为无效分支被提前终止。

---

回溯算法三部曲

回溯算法是解决组合、排列、子集等问题的经典方法。它的核心思想是递归地尝试所有可能的选择，并通过“撤销选择”回到之前的状态，从而穷举所有解。其实现过程可以总结为以下三个关键步骤：

---

1. 路径选择：记录当前路径

在每一步递归中，将当前的选择加入路径（通常是一个数组），表示“当前正在尝试这个选择”。
对应代码：path.push(i)
作用：保存当前递归层的选择，用于后续判断是否满足条件。
示例：在组合问题中，选择数字 i 加入 path，表示尝试将 i 作为组合的一部分。

---

2. 递归探索：进入下一层决策

基于当前路径，递归调用函数，处理下一个选择（比如下一个数字或位置）。
对应代码：dfs(i + 1, sum + i)
作用：进入下一层递归，继续尝试剩余的选择。
示例：在组合问题中，递归时从 i+1 开始，确保数字不重复且递增，避免重复组合。

---

3. 撤销选择：回溯到上一层

当递归返回后（即完成当前分支的探索），将最后加入路径的元素移除，回到上一层状态，尝试其他可能的选择。
对应代码：path.pop()
作用：撤销当前层的选择，保证路径的正确性，避免污染其他分支。
示例：组合问题中，当尝试完以 i 开头的所有组合后，移除 i，尝试下一个数字。

 代码框架模板

function backtrack(路径, 选择列表) {if (满足终止条件) {将路径加入结果;return;}for (选择 in 选择列表) {做选择：将选择加入路径;backtrack(路径, 新的选择列表); // 进入下一层递归撤销选择：将选择从路径移除;    // 回溯}
}

关键点解析

1. 路径的维护
   path 数组记录当前递归路径的选择，必须通过 push 和 pop 确保状态正确。

2. 递归与回溯的关系
   递归是纵向深入探索一条路径，回溯是横向尝试其他可能的选择。递归的终点是终止条件，回溯的触发点是递归返回后的 pop。

3. 剪枝优化
   在组合问题中，通过以下两种剪枝大幅减少递归次数：

   • 剩余数字不足：path.length + (9 - i + 1) < k
     例如：如果还需要选 2 个数字，但剩余可用数字只有 1 个，直接终止。

   • 和超过目标值：sum + i > n
     当前路径和已经超过 n，无需继续递归

 

---

总结

该问题通过回溯算法枚举所有可能的组合，结合剪枝策略（剩余数字不足、和超过目标值）显著提高效率。核心在于：

1. 递增选择数字：避免重复组合。

2. 剪枝优化：减少不必要的递归调用。

3. 回溯机制：撤销选择以尝试其他可能。

这种模式适用于许多组合问题，如子集、排列、组合总和等。