代码随想录算法训练营第二十一天| 回溯 216. 组合总和 III 17. 电话号码的字母组合
2024-01-07 17:36:07
216. 组合总和 III
可以参考77.组合中关于选取数组的相关操作。
递归函数的返回值以及参数:一般为void类型
递归函数终止条件:path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,然后当n为0的时候(找到数组值为n),终止,将结果导入res中
递归函数单层逻辑:回溯法的搜索过程就是一个树型结构的遍历过程,for循环用来横向遍历,递归的过程是纵向遍历。
class Solution {
public:
vector<vector<int>>res;
void backtracing(vector<int>path,int k,int n,int index){
if(path.size()==k&&!n){
res.push_back(path);
return;
}
for(int i=index;i<=9;i++){
path.push_back(i);
n-=i;
backtracing(path,k,n,i+1);
n+=i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<int>path;
int index=1;
backtracing(path,k,n,index);
return res;
}
};
剪枝操作
如果n为负了,就没有再继续减下去的必要了,可以提前回溯。
for(int i=index;i<=9-(k-path.size())+1;i++){
path.push_back(i);
n-=i;
//提前回溯
if(n<0){
n+=i;
path.pop_back();
return;
}
backtracing(path,k,n,i+1);
n+=i;
path.pop_back();
}
?完整代码:
class Solution {
public:
vector<vector<int>>res;
void backtracing(vector<int>path,int k,int n,int index){
if(path.size()==k&&!n){
res.push_back(path);
return;
}
for(int i=index;i<=9-(k-path.size())+1;i++){
path.push_back(i);
n-=i;
if(n<0){
n+=i;
path.pop_back();
return;
}
backtracing(path,k,n,i+1);
n+=i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<int>path;
int index=1;
backtracing(path,k,n,index);
return res;
}
};
17. 电话号码的字母组合
遇到回溯的题目,首先可以尝试画一下n叉树
确定回溯函数参数:首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。
确定终止条件:到达叶子结点是搜索,即stringg s的长度要与原先输入的长度相等
确定单层遍历逻辑:首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。然后for循环来处理这个字符集。
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> res;
string s;
void backtracing(string digits,int index){
if(index==digits.size()){
res.push_back(s);
return;
}
int num=digits[index]-'0';
string letter=letterMap[num];
for(int i=0;i<letter.size();i++){
s.push_back(letter[i]);
backtracing(digits,index+1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
int index=0;
if(!digits.size()) return res;
backtracing(digits,index);
return res;
}
};
文章来源:https://blog.csdn.net/weixin_47100514/article/details/135429630
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!