216.组合总和III
代码
class Solution { public: vector<vector<int>> result; // 存放符合条件结果的集合 vector<int> path; // 用来存放符合条件结果 int sum; void backtracking(int n, int k, int startIndex) { if (path.size() == k) { if (sum == n) result.push_back(path); return; } for (int i = startIndex; i <= 9; i++) { path.push_back(i); // 处理节点 sum += i; backtracking(n, k, i + 1); // 递归 path.pop_back(); // 回溯,撤销处理的节点 sum -= i; } } vector<vector<int>> combinationSum3(int k, int n) { result.clear(); // 可以不写 path.clear(); // 可以不写 sum = 0; backtracking(n, k, 1); return result; } };
思路
只需要在上题的基础上略作修改,即可完成本题
17.电话号码的字母组合*
代码
示例代码
// 版本一 class Solution { private: const string letterMap[10] = { "", // 0 "", // 1 "abc", // 2 "def", // 3 "ghi", // 4 "jkl", // 5 "mno", // 6 "pqrs", // 7 "tuv", // 8 "wxyz", // 9 }; public: vector<string> result; string s; void backtracking(const string& digits, int index) { if (index == digits.size()) { result.push_back(s); return; } int digit = digits[index] - '0'; // 将index指向的数字转为int string letters = letterMap[digit]; // 取数字对应的字符集 for (int i = 0; i < letters.size(); i++) { s.push_back(letters[i]); // 处理 backtracking(digits, index + 1); // 递归,注意index+1,一下层要处理下一个数字了 s.pop_back(); // 回溯 } } vector<string> letterCombinations(string digits) { s.clear(); result.clear(); if (digits.size() == 0) { return result; } backtracking(digits, 0); return result; } };
思路
递归回溯核心如下:
int digit = digits[index] - '0'; // 将index指向的数字转为int string letters = letterMap[digit]; // 取数字对应的字符集 for (int i = 0; i < letters.size(); i++) { s.push_back(letters[i]); // 处理 backtracking(digits, index + 1); // 递归,注意index+1,一下层要处理下一个数字了 s.pop_back(); // 回溯 }