代码随想录刷题 Day28

216.组合总和III

和前一个题一样，照着自己就能写出来，就多了一个判断结果是不是等于n的逻辑。有两个地方可以剪纸，一个是当和已经大于要找的时候直接返回，另一个是当剩余元素少于三个的时候直接返回（第一层递归是少于三个， 第二层递归是少于两个）

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

 17. Letter Combinations of a Phone Number

注意下string的用法。比如定义string s可以对s做 s[]操作

class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string> result; //这个用来存总共的结果集string s; //这个用来存单个的结果集void backtracking(const string& digits, int index){ //这个二叉树的深度就是index的个数，宽度就是三个字母if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0'; //假如是“23”，这里就取出来了2，因为主函数一开始的index是0就是这个字符串第一个数string letters = letterMap[digit]; //这句写不出来；for (int i = 0; i < letters.size(); i++ ) {s.push_back(letters[i]);backtracking(digits, index + 1);//s.pop_back(letters[i]); 这句写错了s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0)return result;backtracking(digits,0);return result;}
};