day25回溯算法part02| 216.组合总和III 17.电话号码的字母组合

216.组合总和III

题目链接/文章讲解 | 视频讲解

class Solution {
public:vector<vector<int>> result;vector<int> path;int sum;void backtracking(int n, int k, int startindex) {// int sum = accumulate(path.begin(), path.end(), 0);if (sum == n && path.size() == k) {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) {backtracking(n, k, 1);return result;}
};

17.电话号码的字母组合

题目链接/文章讲解 | 视频讲解
这题自己参考前面组合总数的题目自己做出来的

class Solution {
public:const string letterMap[10] = {"","","abc", //2"def", //3"ghi", //4"jkl", //5"mno", //6"pqrs",//7"tuv", //8"wxyz", //9};vector<string> result;string path;void backtracking(const string& digits, int startindex) {// 结束条件，是否等与digits的长度if (path.size() == digits.size()) {result.push_back(path);return;}string str = letterMap[digits[startindex] - '0'];for (int i = 0; i < str.size(); i++) {path += str[i];backtracking(digits, startindex+1);path.erase(path.end() - 1);}}vector<string> letterCombinations(string digits) {if (digits == "") return result;backtracking(digits, 0);return result;}
};