代码随想录22| 216.组合总和III， 17.电话号码的字母组合

216.组合总和III

题目链接/文章讲解：链接地址
视频讲解：链接地址

代码思路：回溯三部曲：
1.确定函数参数：n,k,sum,startIndex;
2.结束条件，path == k,并且如果sum==n 结束递归
3.递归回溯逻辑。

class Solution {vector<int> path;vector<vector<int>> result; private:void back_tracking(int k, int n, int startIndex, int sum) {if (path.size() == k) {if (sum == n) result.push_back(path);return;}for (int i = startIndex; i <= 9; i++) {sum += i;path.push_back(i);back_tracking(k, n, i + 1, sum);sum -= i;path.pop_back();}}public:vector<vector<int>> combinationSum3(int k, int n) {int sum;back_tracking(k, n, 1, sum);return  result;}
};

17.电话号码的字母组合

题目链接/文章讲解：链接地址
视频讲解：链接地址

代码思路：传入参数：输入的数字，第几个数字的索引
结束条件：第几个数字的索引等于输入数字的长度
递归回溯：先找到创建的数字Map的索引，然后找到对应数字下的字符进行遍历递归。

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};string s;vector<string> result; void back_traking(string digits, int index) {if (index == digits.size()) {result.push_back(s);return;}//转数字int numIndex = digits[index] - '0';//映射数字对应的字符string stringNum = letterMap[numIndex];for (int i = 0; i < stringNum.size(); i++) {s.push_back(stringNum[i]);back_traking(digits, index + 1);s.pop_back();}}
public:vector<string> letterCombinations(string digits) {if (digits == "") return result;back_traking(digits,0);return result;}
};