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.电话号码的字母组合
题目链接/文章讲解:链接地址
视频讲解:链接地址文章来源:https://www.toymoban.com/news/detail-670039.html
代码思路:传入参数:输入的数字,第几个数字的索引
结束条件:第几个数字的索引等于输入数字的长度
递归回溯:先找到创建的数字Map的索引,然后找到对应数字下的字符进行遍历递归。文章来源地址https://www.toymoban.com/news/detail-670039.html
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;
}
};
到了这里,关于代码随想录22| 216.组合总和III, 17.电话号码的字母组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!