上饶有哪些做网站的公司,昆明网站制作计划,在internet上建设网站,wordpress前台注册登入前言
回溯算法中递归的逻辑不重要#xff0c;只要掌握回溯的模板以及将问题转化为树形图#xff0c;整个问题就很好解决了#xff0c;比二叉树简单。 Leetcode 77 组合
题目链接#xff1a;77. 组合 - 力扣#xff08;LeetCode#xff09;
代码随想录题解#xff1a;…前言
回溯算法中递归的逻辑不重要只要掌握回溯的模板以及将问题转化为树形图整个问题就很好解决了比二叉树简单。 Leetcode 77 组合
题目链接77. 组合 - 力扣LeetCode
代码随想录题解代码随想录 (programmercarl.com)
思路套回溯的模板终止条件是pathk。然后将题目描述的组合逻辑想象成树形结构
代码
class Solution {
public:vectorint path;vectorvectorintres;void backtracking(int n,int k, int index){if(path.size()k)//终止条件{res.push_back(path);return;}for(int iindex;in;i)树形结构逻辑{path.push_back(i);backtracking(n, k, i1);path.pop_back();回溯}return;}vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return res;}
};
Leetcode 216 组合总和Ⅲ
题目链接216. 组合总和 III - 力扣LeetCode
代码随想录题解代码随想录 (programmercarl.com)
思路这个题和上一道题唯一的区别就是终止条件加了一个和等于目标值树形结构基本没变 代码
class Solution {
public:vectorint path;vectorvectorintres;int sum0;void backtracking(int k,int n,int index){if(sumnpath.size()k)//终止条件{res.push_back(path);return;}for(int iindex;i9;i)树形结构逻辑{path.push_back(i);sumi;backtracking(k, n, i1);sum-i;//回溯path.pop_back();}return;} vectorvectorint combinationSum3(int k, int n) {backtracking(k, n, 1);return res;}
};
Leetcode17 电话号码的字母组合
题目链接17. 电话号码的字母组合 - 力扣LeetCode
代码随想录题解代码随想录 (programmercarl.com)
思路这道题目的终止条件和上面三道题几乎一样只不过树形逻辑要通过一个二维字符串数组做一个映射。 代码
class Solution {
public:string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};string path;vectorstring res;void backtracking(string a,int index){if(path.size()a.size())//终止条件{res.push_back(path);return;}int digita[index]-0;//映射string letterletterMap[digit];for(int i0;iletter.size();i)//树形结构逻辑{path.push_back(letter[i]);backtracking(a, index1);path.pop_back();//回溯}return;}vectorstring letterCombinations(string digits) {if(digits.size()0){return res;}backtracking(digits, 0);return res;}};
总结
求解回溯模板需要想好终止条件以及树形逻辑的代码编写不需要仔细思考递归逻辑相比于二叉树的各种遍历简单许多。
