当前位置：首页 > news >正文

今日算法（组合问题III）（回溯的使用）

news 2026/5/25 0:03:26

题目描述

找出所有相加之和为n的k个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字最多使用一次
返回所有可能的有效组合的列表，列表不能包含相同的组合两次，组合可以以任何顺序返回

核心思路：带双重剪枝的回溯法

这道题是LeetCode 77. 组合的进阶版，本质还是组合枚举问题，只是在 "选 k 个数" 的基础上，增加了 "和为 n" 的约束条件。

回溯三要素

路径：用path保存当前正在构建的组合，sum保存当前组合的和
选择列表：从start位置开始选择数字（保证组合递增，避免重复）
终止条件：
- 当path.size() == k且sum == n：找到有效组合，加入结果集
- 当path.size() == k但sum != n：无效组合，直接返回

双重剪枝优化（必加，大幅提升效率）

和剪枝：如果当前和sum + i > n，后面的数字都比i大，加起来肯定超过n，直接终止循环
数量剪枝：剩余需要选need = k - path.size()个数字，因此i最大只能到9 - need + 1，否则后面不够选need个数字

完整代码实现（C++）

cpp

class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; // 存储所有结果 vector<int> path; // 存储当前正在构建的组合 backtrack(k, n, 1, 0, path, res); return res; } private: // start: 本轮可以选择的起始位置 // sum: 当前组合的和 void backtrack(int k, int n, int start, int sum, vector<int>& path, vector<vector<int>>& res) { // 1. 递归终止条件：选够了k个数 if (path.size() == k) { if (sum == n) { res.push_back(path); // 和为n，加入结果集 } return; } // 2. 双重剪枝优化 // 剪枝1：数量剪枝，剩余数字不够选need个 int need = k - path.size(); // 剪枝2：和剪枝，当前和+i超过n，后面更大的数字不用看了 for (int i = start; i <= 9 - need + 1 && sum + i <= n; ++i) { // 3. 选择当前数字 path.push_back(i); // 4. 递归：下一轮从i+1开始选择（避免重复） backtrack(k, n, i + 1, sum + i, path, res); // 5. 回溯：撤销选择，尝试下一个数字 path.pop_back(); } } };

详细执行流程解析

以示例 2k=3, n=9为例，模拟回溯过程：

初始状态

res = []，path = []，start = 1，sum = 0

递归过程

第一层递归（start=1，path=[]，sum=0）
- need = 3，循环i从1到7（9-3+1=7）
- i=1：
  - path = [1]，sum = 1，进入第二层递归，start=2
  - 第二层need = 2，循环i从2到8
    - i=2：
      - path = [1,2]，sum = 3，进入第三层递归，start=3
      - 第三层need = 1，循环i从3到9
        i=3：sum+3=6 < 9，path=[1,2,3]，长度 3，和 6≠9，返回
        i=4：sum+4=7 < 9，path=[1,2,4]，和 7≠9，返回
        i=5：sum+5=8 < 9，path=[1,2,5]，和 8≠9，返回
        i=6：sum+6=9 == 9，path=[1,2,6]，加入res，返回
      - 回溯，path=[1,2]
    - i=3：
      - path = [1,3]，sum = 4，进入第三层递归，start=4
      - i=5：sum+5=9 == 9，path=[1,3,5]，加入res
    - i=4：
      - path = [1,4]，sum = 5，进入第三层递归，start=5
      - 所有i加起来都超过 9，无结果
  - 回溯，path=[1]
- i=2：
  - path = [2]，sum = 2，进入第二层递归，start=3
  - i=3：
    - path = [2,3]，sum = 5，进入第三层递归，start=4
    - i=4：sum+4=9 == 9，path=[2,3,4]，加入res
- 后续i均无有效组合

最终结果

res = [[1,2,6],[1,3,5],[2,3,4]]，与示例输出完全一致。

关键细节与易错点

start参数的作用每次递归从start位置开始选择，保证组合中的元素是递增的，避免出现[2,1,3]这种重复组合。
双重剪枝的必要性
- 数量剪枝：避免无效的循环，例如当还需要选 3 个数字时，i最大只能到 7，因为 8 和 9 只能选 2 个，不够 3 个
- 和剪枝：提前终止不可能满足和条件的分支，大幅减少递归次数
sum的传递方式这里用值传递sum，每次递归传递sum + i，不需要在回溯时手动减i，代码更简洁；如果用引用传递，需要在path.pop_back()后加上sum -= i。
与 LeetCode 77. 组合的对比
- 77 题：只需要选 k 个数，没有和的约束
- 216 题：在 77 题的基础上，增加了和为 n 的约束，以及对应的和剪枝

复杂度分析

时间复杂度：\(O(C(9, k) \times k)\)
- 最多有 \(C(9, k)\) 个有效组合
- 每个组合需要复制一次到结果集，时间复杂度为 \(O(k)\)
空间复杂度：\(O(k)\)
- 递归调用栈的深度等于k，临时路径path的最大长度也为k，不包含结果集的额外空间。

总结

组合总和 III 是组合问题的经典进阶题，核心解法是带双重剪枝的回溯法。通过start参数保证组合不重复，通过数量剪枝和和剪枝大幅优化效率。这道题的思路可以推广到所有组合枚举类问题，是掌握回溯法的必练题目。

迭代法核心思想

递归回溯的本质是深度优先搜索（DFS），而 DFS 可以用栈来模拟实现。我们把递归过程中每一层的状态（起始位置、当前和、当前路径）都保存在栈中，通过不断弹出栈顶元素、压入新状态的方式，模拟递归的入栈和出栈过程。

栈中需要保存的状态

start：本轮可以选择的起始数字（保证组合递增，避免重复）
sum：当前组合的和
path：当前正在构建的组合

迭代法的剪枝优化

和递归法完全一致，我们同样可以加入双重剪枝，大幅减少无效的状态入栈：

数量剪枝：剩余需要选need = k - path.size() - 1个数字，因此i最大只能到9 - need + 1
和剪枝：如果sum + i > n，后面的数字都比i大，加起来肯定超过n，直接终止循环

完整迭代法代码实现（C++）

cpp

class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; // 栈中保存：(起始位置start, 当前和sum, 当前路径path) stack<tuple<int, int, vector<int>>> stk; // 初始状态：从1开始选，和为0，路径为空 stk.emplace(1, 0, vector<int>()); while (!stk.empty()) { // 弹出栈顶元素（模拟递归返回） auto [start, sum, path] = stk.top(); stk.pop(); // 1. 终止条件：选够了k个数 if (path.size() == k) { if (sum == n) { res.push_back(path); // 和为n，加入结果集 } continue; } // 2. 双重剪枝优化 int need = k - path.size(); // 还需要选need个数字 // 遍历所有可能的选择 for (int i = start; i <= 9 - need + 1 && sum + i <= n; ++i) { // 3. 生成新状态，压入栈（模拟递归调用） vector<int> new_path = path; new_path.push_back(i); stk.emplace(i + 1, sum + i, new_path); } } return res; } };

代码逐行解析

栈的初始化
cpp
```
stack<tuple<int, int, vector<int>>> stk; stk.emplace(1, 0, vector<int>());
```
我们用一个三元组栈保存每一层的状态，初始时压入最外层的状态：从数字 1 开始选，当前和为 0，路径为空。
主循环：模拟递归过程
cpp
```
while (!stk.empty()) { auto [start, sum, path] = stk.top(); stk.pop(); // ... }
```
只要栈不为空，就不断弹出栈顶元素进行处理，这对应递归过程中函数的返回。
终止条件处理
cpp
```
if (path.size() == k) { if (sum == n) { res.push_back(path); } continue; }
```
和递归法完全一致：当选够 k 个数时，检查和是否为 n，是的话加入结果集，然后直接跳过后续处理。
状态生成与压栈
cpp
```
for (int i = start; i <= 9 - need + 1 && sum + i <= n; ++i) { vector<int> new_path = path; new_path.push_back(i); stk.emplace(i + 1, sum + i, new_path); }
```
这对应递归过程中的选择和递归调用：
- 生成新的路径new_path，加入当前选择的数字i
- 生成新的状态：下一轮从i+1开始选，和为sum+i，路径为new_path
- 将新状态压入栈，等待后续处理

详细执行流程解析

我们还是以示例 2k=3, n=9为例，模拟迭代法的执行过程：

初始状态

栈：[(1, 0, [])]
结果集：[]

第一步：弹出初始状态

弹出(1, 0, [])
path.size()=0 < 3，need=3
循环i从 1 到 7（9-3+1=7）
压入新状态：(2,1,[1])、(3,2,[2])、(4,3,[3])、(5,4,[4])、(6,5,[5])、(7,6,[6])、(8,7,[7])
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4]), (6,5,[5]), (7,6,[6]), (8,7,[7])]

第二步：弹出栈顶`(8,7,[7])`

path.size()=1 < 3，need=2
循环i从 8 到9-2+1=8
sum+i=7+8=15 > 9，不满足和剪枝，循环不执行
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4]), (6,5,[5]), (7,6,[6])]

第三步：弹出栈顶`(7,6,[6])`

path.size()=1 < 3，need=2
循环i从 7 到 8
i=7：sum+i=6+7=13 >9，不满足
循环不执行
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4]), (6,5,[5])]

第四步：弹出栈顶`(6,5,[5])`

path.size()=1 < 3，need=2
循环i从 6 到 8
i=6：sum+i=5+6=11 >9，不满足
循环不执行
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4])]

第五步：弹出栈顶`(5,4,[4])`

path.size()=1 < 3，need=2
循环i从 5 到 8
i=5：sum+i=4+5=9，压入(6,9,[4,5])
i=6：sum+i=4+6=10 >9，终止循环
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3]), (6,9,[4,5])]

第六步：弹出栈顶`(6,9,[4,5])`

path.size()=2 < 3，need=1
循环i从 6 到 9
sum+i=9+6=15 >9，不满足
循环不执行
栈现在：[(2,1,[1]), (3,2,[2]), (4,3,[3])]

第七步：弹出栈顶`(4,3,[3])`

path.size()=1 < 3，need=2
循环i从 4 到 8
i=4：sum+i=3+4=7，压入(5,7,[3,4])
i=5：sum+i=3+5=8，压入(6,8,[3,5])
i=6：sum+i=3+6=9，压入(7,9,[3,6])
i=7：sum+i=3+7=10 >9，终止循环
栈现在：[(2,1,[1]), (3,2,[2]), (5,7,[3,4]), (6,8,[3,5]), (7,9,[3,6])]

后续过程

继续按照这个逻辑弹出和压入状态，最终会依次找到[2,3,4]、[1,3,5]、[1,2,6]三个有效组合，和示例输出完全一致。

递归法 vs 迭代法对比

表格

对比维度	递归回溯法	迭代法
代码简洁度	非常简洁，逻辑清晰	稍复杂，需要手动管理栈
理解难度	容易理解，符合人类思维	需要理解递归的栈模拟过程
栈溢出风险	递归深度最大为 9，无风险	无栈溢出风险
效率	几乎一致（都有双重剪枝）	几乎一致
适用场景	大多数回溯问题	递归深度过大的场景，或不允许使用递归的场景