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

题目描述找出所有相加之和为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个数字完整代码实现Ccppclass Solution { public: vectorvectorint combinationSum3(int k, int n) { vectorvectorint res; // 存储所有结果 vectorint path; // 存储当前正在构建的组合 backtrack(k, n, 1, 0, path, res); return res; } private: // start: 本轮可以选择的起始位置 // sum: 当前组合的和 void backtrack(int k, int n, int start, int sum, vectorint path, vectorvectorint 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. 递归下一轮从i1开始选择避免重复 backtrack(k, n, i 1, sum i, path, res); // 5. 回溯撤销选择尝试下一个数字 path.pop_back(); } } };详细执行流程解析以示例 2k3, n9为例模拟回溯过程初始状态res []path []start 1sum 0递归过程第一层递归start1path[]sum0need 3循环i从1到79-317i1path [1]sum 1进入第二层递归start2第二层need 2循环i从2到8i2path [1,2]sum 3进入第三层递归start3第三层need 1循环i从3到9i3sum36 9path[1,2,3]长度 3和 6≠9返回i4sum47 9path[1,2,4]和 7≠9返回i5sum58 9path[1,2,5]和 8≠9返回i6sum69 9path[1,2,6]加入res返回回溯path[1,2]i3path [1,3]sum 4进入第三层递归start4i5sum59 9path[1,3,5]加入resi4path [1,4]sum 5进入第三层递归start5所有i加起来都超过 9无结果回溯path[1]i2path [2]sum 2进入第二层递归start3i3path [2,3]sum 5进入第三层递归start4i4sum49 9path[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直接终止循环完整迭代法代码实现Ccppclass Solution { public: vectorvectorint combinationSum3(int k, int n) { vectorvectorint res; // 栈中保存(起始位置start, 当前和sum, 当前路径path) stacktupleint, int, vectorint stk; // 初始状态从1开始选和为0路径为空 stk.emplace(1, 0, vectorint()); 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. 生成新状态压入栈模拟递归调用 vectorint new_path path; new_path.push_back(i); stk.emplace(i 1, sum i, new_path); } } return res; } };代码逐行解析栈的初始化cppstacktupleint, int, vectorint stk; stk.emplace(1, 0, vectorint());我们用一个三元组栈保存每一层的状态初始时压入最外层的状态从数字 1 开始选当前和为 0路径为空。主循环模拟递归过程cppwhile (!stk.empty()) { auto [start, sum, path] stk.top(); stk.pop(); // ... }只要栈不为空就不断弹出栈顶元素进行处理这对应递归过程中函数的返回。终止条件处理cppif (path.size() k) { if (sum n) { res.push_back(path); } continue; }和递归法完全一致当选够 k 个数时检查和是否为 n是的话加入结果集然后直接跳过后续处理。状态生成与压栈cppfor (int i start; i 9 - need 1 sum i n; i) { vectorint new_path path; new_path.push_back(i); stk.emplace(i 1, sum i, new_path); }这对应递归过程中的选择和递归调用生成新的路径new_path加入当前选择的数字i生成新的状态下一轮从i1开始选和为sumi路径为new_path将新状态压入栈等待后续处理详细执行流程解析我们还是以示例 2k3, n9为例模拟迭代法的执行过程初始状态栈[(1, 0, [])]结果集[]第一步弹出初始状态弹出(1, 0, [])path.size()0 3need3循环i从 1 到 79-317压入新状态(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 3need2循环i从 8 到9-218sumi7815 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 3need2循环i从 7 到 8i7sumi6713 9不满足循环不执行栈现在[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4]), (6,5,[5])]第四步弹出栈顶(6,5,[5])path.size()1 3need2循环i从 6 到 8i6sumi5611 9不满足循环不执行栈现在[(2,1,[1]), (3,2,[2]), (4,3,[3]), (5,4,[4])]第五步弹出栈顶(5,4,[4])path.size()1 3need2循环i从 5 到 8i5sumi459压入(6,9,[4,5])i6sumi4610 9终止循环栈现在[(2,1,[1]), (3,2,[2]), (4,3,[3]), (6,9,[4,5])]第六步弹出栈顶(6,9,[4,5])path.size()2 3need1循环i从 6 到 9sumi9615 9不满足循环不执行栈现在[(2,1,[1]), (3,2,[2]), (4,3,[3])]第七步弹出栈顶(4,3,[3])path.size()1 3need2循环i从 4 到 8i4sumi347压入(5,7,[3,4])i5sumi358压入(6,8,[3,5])i6sumi369压入(7,9,[3,6])i7sumi3710 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无风险无栈溢出风险效率几乎一致都有双重剪枝几乎一致适用场景大多数回溯问题递归深度过大的场景或不允许使用递归的场景总结迭代法实现回溯的核心是用栈模拟递归的状态转移。对于这道题来说递归法已经足够优秀但掌握迭代法可以让我们更深入地理解回溯的本质也能应对一些特殊场景如递归深度限制。