216.组合总和III
这道题我一开始写的时候觉得和昨天的那道题很像，就模仿着写了一遍。写出来之后，发现没有考虑vector里数值重复这件事。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(int k, int n, int start_index){
if(path.size() == k){
int cur_sum = 0;
for(int i=0; i<path.size(); i++){
cur_sum = cur_sum + path[i];
}
if(cur_sum == n){
res.push_back(path);
}
return ;
}
for(int j=start_index; j<=9; j++){
path.push_back(j);
backtracking(k,n,start_index+1);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k,n,1);
return res;
}
};
找了好半天，开始的时候我还以为是我两个forloop里面都用了i而产生了bug，但其实这不是问题。问题是出在了call backtracking(k,n,start_index+1)这一行。不应该是start_index+1，而是j+1。这是概念上理解出现了错误。 剪枝操作的使用是当当前sum大于target sum也不可能有结果，不管当前path里有几个数。
17.电话号码的字母组合
Yeah！独立做出来啦。
写的时候遇到的几个问题：
- 光顾着写for loop了，要运行的时候才发现还没写终止条件呢。运行了发现终止条件忘了加return了。
- 由于vector从0开始数，而手机键位从1开始数，所以计算cur_sum的时候要-1才能对应上我写的table。
- 要记得考虑edge case，也就是digits size是0的话，应该直接返回空数组，而不是一个包含“”的的数组。
class Solution { public: vector<string> res; string path = ""; vector<string> table{"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; void backtracking(string digits, int cur_index){ if(cur_index == digits.length()){ res.push_back(path); return ; } int cur_num = digits[cur_index] - '0'-1; for(int j=0; j<table[cur_num].size(); j++){ path.push_back(table[cur_num][j]); backtracking(digits,cur_index+1); path.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits.size() == 0){ return res; } backtracking(digits,0); return res; } };
