php网站屏蔽词怎么做,免费加盟无需店面,石岩小学网站建设,如何建设局域网网站216. 组合总和 III
可以参考77.组合中关于选取数组的相关操作。
递归函数的返回值以及参数#xff1a;一般为void类型
递归函数终止条件#xff1a;path这个数组的大小如果达到k#xff0c;说明我们找到了一个子集大小为k的组合了#xff0c;然后当n为0的时候#xff0…216. 组合总和 III
可以参考77.组合中关于选取数组的相关操作。
递归函数的返回值以及参数一般为void类型
递归函数终止条件path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了然后当n为0的时候找到数组值为n终止将结果导入res中
递归函数单层逻辑回溯法的搜索过程就是一个树型结构的遍历过程for循环用来横向遍历递归的过程是纵向遍历。
class Solution {
public:vectorvectorintres;void backtracing(vectorintpath,int k,int n,int index){if(path.size()k!n){res.push_back(path);return;}for(int iindex;i9;i){path.push_back(i);n-i;backtracing(path,k,n,i1);ni;path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {vectorintpath;int index1;backtracing(path,k,n,index);return res;}
};
剪枝操作 如果n为负了就没有再继续减下去的必要了可以提前回溯。 for(int iindex;i9-(k-path.size())1;i){path.push_back(i);n-i;//提前回溯if(n0){ni;path.pop_back();return;}backtracing(path,k,n,i1);ni;path.pop_back();} 完整代码
class Solution {
public:vectorvectorintres;void backtracing(vectorintpath,int k,int n,int index){if(path.size()k!n){res.push_back(path);return;}for(int iindex;i9-(k-path.size())1;i){path.push_back(i);n-i;if(n0){ni;path.pop_back();return;}backtracing(path,k,n,i1);ni;path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {vectorintpath;int index1;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, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};vectorstring res;string s;void backtracing(string digits,int index){if(indexdigits.size()){res.push_back(s);return;}int numdigits[index]-0;string letterletterMap[num];for(int i0;iletter.size();i){s.push_back(letter[i]);backtracing(digits,index1);s.pop_back();}}vectorstring letterCombinations(string digits) {int index0;if(!digits.size()) return res;backtracing(digits,index);return res;}
};
