77. 组合给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。class Solution { public: vectorint path; // 单层路径存储当前组合 vectorvectorint ans; // 结果集存储所有符合条件的组合 // 回溯函数 // n: 总数 // k: 需要选取的个数 // startIndex: 当前搜索的起始位置防止重复选取保证组合有序 void backtracking(int n, int k, int startIndex) { // 1. 终止条件当前组合长度等于 k收集结果 if (path.size() k) { ans.push_back(path); return; } // 2. 单层搜索逻辑 // 剪枝优化i n - (k - path.size()) 1 // 解释还需要选取 (k - path.size()) 个元素 // 如果 i 超过了这个范围剩下的元素就不够凑齐 k 个了 for (int i startIndex; i n - (k - path.size()) 1; i) { path.push_back(i); // 处理节点 backtracking(n, k, i 1); // 递归下一层从 i1 开始 path.pop_back(); // 回溯撤销处理结果 } } vectorvectorint combine(int n, int k) { backtracking(n, k, 1); return ans; } };总结1. 回溯三部曲确定返回值和参数返回值通常为void参数根据题目需求定这里是范围n、目标数量k、起始位置startIndex。确定终止条件当路径长度满足要求path.size() k时保存结果并返回。确定单层搜索逻辑for循环横向遍历从startIndex到n。backtracking递归纵向遍历。核心path.push_back和path.pop_back构成了回溯的“做选择”与“撤销选择”。2. 剪枝优化代码中i n - (k - path.size()) 1是一个极其重要的优化。场景假设n4, k3当前path为空。无剪枝i会遍历 1 到 4。当i4时path{4}递归下一层发现没有元素可选了最终只能得到一个长度为 1 的无效路径。有剪枝还需要选k - path.size() 3个数。为了至少能有 3 个数起始位置i最大只能是4 - 3 1 2。所以i只需遍历 1 和 2直接跳过了 3 和 4大幅减少了无效递归。3. 复杂度分析时间复杂度O(C(n, k) * k)。共有 C(n, k) 个组合每个组合需要 O(k) 的时间存入结果集。空间复杂度O(k)。递归深度为 kpath 最大长度也为 k不考虑结果集占用的空间。216. 组合总和 III找出所有相加之和为n的k个数的组合且满足下列条件只使用数字1到9每个数字 最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次组合可以以任何顺序返回。class Solution { public: vectorint path; // 单层路径 vectorvectorint ans; // 结果集 // 回溯函数 // k: 目标个数 // n: 目标和 // startIndex: 起始位置 // sum: 当前路径累加和 void backtracking(int k, int n, int startIndex, int sum) { // 1. 终止条件已选够 k 个数 if (path.size() k) { if (sum n) ans.push_back(path); // 满足和的条件才收集 return; } // 2. 单层搜索逻辑 // 剪枝优化1i 9 - (k - path.size()) 1 // 保证剩余数字足够凑齐 k 个避免无效递归 for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝优化2如果当前和已超标直接返回 if (sum i n) return; path.push_back(i); // 处理节点 backtracking(k, n, i 1, sum i); // 递归 path.pop_back(); // 回溯 } } vectorvectorint combinationSum3(int k, int n) { backtracking(k, n, 1, 0); return ans; } };总结1. 本题与上一题的区别这道题是 216. 组合总和 III可以看作是 77. 组合 的变体组合问题依然是从集合中选 k 个数这里是 1-9。增加约束不仅要选够 k 个还要满足和 n。参数变化回溯函数多了一个sum参数用于实时记录当前路径的和避免了每次遍历数组求和的开销。2. 剪枝优化双重剪枝总和剪枝 (sum i n)因为数字是正数且递增如果加上当前的i已经爆了后面的i1, i2...更大肯定也会爆所以直接return结束当前层循环。数量剪枝 如果剩下的数字不够凑齐k个就没必要遍历了可以优化为i 9 - (k - path.size()) 1。3. 为什么要传递sum在递归参数中直接维护sum是回溯常用的技巧对比如果在终止条件里写if (path.size() k accumulate(path.begin(), path.end(), 0) n)每次都要遍历 path 计算总和时间复杂度较高。优化通过传参sum i我们在 O(1) 时间内完成了和的更新与判断。4. 复杂度分析时间复杂度O(C(9, k) * k)。最多有 C(9, k) 种组合每个组合需要 O(k) 时间复制到结果。空间复杂度O(k)。递归深度和 path 长度均为 k。17. 电话号码的字母组合给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。class Solution { public: // 数字到字母的映射表索引 0 和 1 为空 vectorstring mp {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; string path; // 当前拼接的字符串路径 vectorstring ans; // 结果集 // 回溯函数 // digits: 输入的数字字符串 // index: 当前处理到 digits 的第几个数字树的深度 void backtracking(string digits, int index) { // 1. 终止条件路径长度等于数字串长度说明处理完了所有数字 if (path.size() digits.size()) { ans.push_back(path); return; } // 边界检查防止越界虽然上面的判断已经隐含了这个逻辑作为一个好习惯保留 if (index digits.size()) return; // 2. 单层搜索逻辑 // 获取当前数字对应的字母字符串 string s mp[digits[index] - 0]; // 遍历当前数字对应的所有字母 for (char c : s) { path.push_back(c); // 处理节点 backtracking(digits, index 1);// 递归处理下一个数字 path.pop_back(); // 回溯撤销处理结果 } } vectorstring letterCombinations(string digits) { // 特殊情况处理如果输入为空直接返回空结果 if (digits.empty()) return ans; backtracking(digits, 0); return ans; } };总结1. 树形结构的理解树的宽度由当前数字对应的字母个数决定例如 “2” 对应 “abc”宽度为 3。树的深度由输入数字字符串digits的长度决定。区别之前的“组合问题”是通过startIndex控制不再选取之前的元素纵向遍历而本题是两个不同集合之间的组合横向遍历每一层代表一个数字位所以用index来控制层级即可。2. 细节处理字符转数字digits[index] - 0是经典写法将字符型数字转为整型索引。3. 复杂度分析时间复杂度O(3^m * 4^n)。其中 m 是对应 3 个字母的数字个数n 是对应 4 个字母的数字个数7 和 9。因为每个数字对应的字母个数不同这是一个指数级的复杂度。空间复杂度O(m n)。主要是递归调用的栈空间消耗。
代码随想录算法训练营 Day19 | 回溯算法 part01
77. 组合给定两个整数n和k返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。class Solution { public: vectorint path; // 单层路径存储当前组合 vectorvectorint ans; // 结果集存储所有符合条件的组合 // 回溯函数 // n: 总数 // k: 需要选取的个数 // startIndex: 当前搜索的起始位置防止重复选取保证组合有序 void backtracking(int n, int k, int startIndex) { // 1. 终止条件当前组合长度等于 k收集结果 if (path.size() k) { ans.push_back(path); return; } // 2. 单层搜索逻辑 // 剪枝优化i n - (k - path.size()) 1 // 解释还需要选取 (k - path.size()) 个元素 // 如果 i 超过了这个范围剩下的元素就不够凑齐 k 个了 for (int i startIndex; i n - (k - path.size()) 1; i) { path.push_back(i); // 处理节点 backtracking(n, k, i 1); // 递归下一层从 i1 开始 path.pop_back(); // 回溯撤销处理结果 } } vectorvectorint combine(int n, int k) { backtracking(n, k, 1); return ans; } };总结1. 回溯三部曲确定返回值和参数返回值通常为void参数根据题目需求定这里是范围n、目标数量k、起始位置startIndex。确定终止条件当路径长度满足要求path.size() k时保存结果并返回。确定单层搜索逻辑for循环横向遍历从startIndex到n。backtracking递归纵向遍历。核心path.push_back和path.pop_back构成了回溯的“做选择”与“撤销选择”。2. 剪枝优化代码中i n - (k - path.size()) 1是一个极其重要的优化。场景假设n4, k3当前path为空。无剪枝i会遍历 1 到 4。当i4时path{4}递归下一层发现没有元素可选了最终只能得到一个长度为 1 的无效路径。有剪枝还需要选k - path.size() 3个数。为了至少能有 3 个数起始位置i最大只能是4 - 3 1 2。所以i只需遍历 1 和 2直接跳过了 3 和 4大幅减少了无效递归。3. 复杂度分析时间复杂度O(C(n, k) * k)。共有 C(n, k) 个组合每个组合需要 O(k) 的时间存入结果集。空间复杂度O(k)。递归深度为 kpath 最大长度也为 k不考虑结果集占用的空间。216. 组合总和 III找出所有相加之和为n的k个数的组合且满足下列条件只使用数字1到9每个数字 最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次组合可以以任何顺序返回。class Solution { public: vectorint path; // 单层路径 vectorvectorint ans; // 结果集 // 回溯函数 // k: 目标个数 // n: 目标和 // startIndex: 起始位置 // sum: 当前路径累加和 void backtracking(int k, int n, int startIndex, int sum) { // 1. 终止条件已选够 k 个数 if (path.size() k) { if (sum n) ans.push_back(path); // 满足和的条件才收集 return; } // 2. 单层搜索逻辑 // 剪枝优化1i 9 - (k - path.size()) 1 // 保证剩余数字足够凑齐 k 个避免无效递归 for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝优化2如果当前和已超标直接返回 if (sum i n) return; path.push_back(i); // 处理节点 backtracking(k, n, i 1, sum i); // 递归 path.pop_back(); // 回溯 } } vectorvectorint combinationSum3(int k, int n) { backtracking(k, n, 1, 0); return ans; } };总结1. 本题与上一题的区别这道题是 216. 组合总和 III可以看作是 77. 组合 的变体组合问题依然是从集合中选 k 个数这里是 1-9。增加约束不仅要选够 k 个还要满足和 n。参数变化回溯函数多了一个sum参数用于实时记录当前路径的和避免了每次遍历数组求和的开销。2. 剪枝优化双重剪枝总和剪枝 (sum i n)因为数字是正数且递增如果加上当前的i已经爆了后面的i1, i2...更大肯定也会爆所以直接return结束当前层循环。数量剪枝 如果剩下的数字不够凑齐k个就没必要遍历了可以优化为i 9 - (k - path.size()) 1。3. 为什么要传递sum在递归参数中直接维护sum是回溯常用的技巧对比如果在终止条件里写if (path.size() k accumulate(path.begin(), path.end(), 0) n)每次都要遍历 path 计算总和时间复杂度较高。优化通过传参sum i我们在 O(1) 时间内完成了和的更新与判断。4. 复杂度分析时间复杂度O(C(9, k) * k)。最多有 C(9, k) 种组合每个组合需要 O(k) 时间复制到结果。空间复杂度O(k)。递归深度和 path 长度均为 k。17. 电话号码的字母组合给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。class Solution { public: // 数字到字母的映射表索引 0 和 1 为空 vectorstring mp {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; string path; // 当前拼接的字符串路径 vectorstring ans; // 结果集 // 回溯函数 // digits: 输入的数字字符串 // index: 当前处理到 digits 的第几个数字树的深度 void backtracking(string digits, int index) { // 1. 终止条件路径长度等于数字串长度说明处理完了所有数字 if (path.size() digits.size()) { ans.push_back(path); return; } // 边界检查防止越界虽然上面的判断已经隐含了这个逻辑作为一个好习惯保留 if (index digits.size()) return; // 2. 单层搜索逻辑 // 获取当前数字对应的字母字符串 string s mp[digits[index] - 0]; // 遍历当前数字对应的所有字母 for (char c : s) { path.push_back(c); // 处理节点 backtracking(digits, index 1);// 递归处理下一个数字 path.pop_back(); // 回溯撤销处理结果 } } vectorstring letterCombinations(string digits) { // 特殊情况处理如果输入为空直接返回空结果 if (digits.empty()) return ans; backtracking(digits, 0); return ans; } };总结1. 树形结构的理解树的宽度由当前数字对应的字母个数决定例如 “2” 对应 “abc”宽度为 3。树的深度由输入数字字符串digits的长度决定。区别之前的“组合问题”是通过startIndex控制不再选取之前的元素纵向遍历而本题是两个不同集合之间的组合横向遍历每一层代表一个数字位所以用index来控制层级即可。2. 细节处理字符转数字digits[index] - 0是经典写法将字符型数字转为整型索引。3. 复杂度分析时间复杂度O(3^m * 4^n)。其中 m 是对应 3 个字母的数字个数n 是对应 4 个字母的数字个数7 和 9。因为每个数字对应的字母个数不同这是一个指数级的复杂度。空间复杂度O(m n)。主要是递归调用的栈空间消耗。
