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;
}
};