代码随想录算法训练营Day22 | Leetcode 77 组合 Leetcode 216 组合总和Ⅲ Leetcode17 电话号码的字母组合

前言

回溯算法中递归的逻辑不重要，只要掌握回溯的模板以及将问题转化为树形图，整个问题就很好解决了，比二叉树简单。

 Leetcode 77 组合

题目链接：77. 组合 - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：套回溯的模板，终止条件是path==k。然后将题目描述的组合逻辑想象成树形结构

代码：

class Solution {
public:vector<int> path;vector<vector<int>>res;void backtracking(int n,int k, int index){if(path.size()==k)//终止条件{res.push_back(path);return;}for(int i=index;i<=n;i++)树形结构逻辑{path.push_back(i);backtracking(n, k, i+1);path.pop_back();回溯}return;}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return res;}
};

Leetcode 216 组合总和Ⅲ

题目链接：216. 组合总和 III - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：这个题和上一道题唯一的区别就是终止条件加了一个和等于目标值，树形结构基本没变

代码：

class Solution {
public:vector<int> path;vector<vector<int>>res;int sum=0;void backtracking(int k,int n,int index){if(sum==n&&path.size()==k)//终止条件{res.push_back(path);return;}for(int i=index;i<=9;i++)树形结构逻辑{path.push_back(i);sum+=i;backtracking(k, n, i+1);sum-=i;//回溯path.pop_back();}return;}    vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return res;}
};

Leetcode17 电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）

代码随想录题解：代码随想录 (programmercarl.com)

思路：这道题目的终止条件和上面三道题几乎一样，只不过树形逻辑要通过一个二维字符串数组做一个映射。

代码：

class Solution {
public:string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};string path;vector<string> res;void backtracking(string a,int index){if(path.size()==a.size())//终止条件{res.push_back(path);return;}int digit=a[index]-'0';//映射string letter=letterMap[digit];for(int i=0;i<letter.size();i++)//树形结构逻辑{path.push_back(letter[i]);backtracking(a, index+1);path.pop_back();//回溯}return;}vector<string> letterCombinations(string digits) {if(digits.size()==0){return res;}backtracking(digits, 0);return res;}};

总结

求解回溯模板需要想好终止条件以及树形逻辑的代码编写，不需要仔细思考递归逻辑，相比于二叉树的各种遍历简单许多。