代码随想录训练营第二十九天| 77.组合 216.组合总和lll 17.电话号码的字母组合
77.组合：
文档讲解：代码随想录|77.组合
视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
状态：已做出
思路：
这道题目要求把所有的组合情况都列出来，所以需要暴力枚举，暴力枚举如果只是单纯使用多层嵌套for循环的话没有办法了去应对多个组合数，因为for循环嵌套层数是根据组合的个数来定的，如果题目给出的是n个组合数的组合，就需要嵌套n层循环。所以这道题目文档所给出的解法就是使用回溯来解决，回溯就是利用递归函数把整个题目都模仿为多叉树遍历的题目，题目给出的组合数个数就是这颗树的深度，给出的选取范围就是树的宽度。首先设置一个全局变量，这个全局变量是用来保存各种组合情况的，我的递归函数参数分别设置了三个，一个是用来保存单层递归的组合情况，一个用来记录每层的起始点，一个用来记录最后结束点，递归结束的条件是当单层个数达到要求的组合个数，每一层都使用for循环来对一层的节点进行遍历，剪枝操作是使用一个遍历记录此层的剩下需要遍历节点个数，判断剩下的范围是否大于等于剩余个数，小于的话就进行剪枝操作。这些就是回溯的大概操作。
代码如下：
class Solution {
public:vector<vector<int>>result;//递归回溯void dfs(vector<int>&cur,int left,int right,int k) {//当组合个数等于要求个数后结束递归并把此时的值存入result数组里if(cur.size()==k) {result.push_back(cur);return;}int num=right-left+1;if(cur.size()+num<k) return;//这里是进行剪枝操作//这里是使用for循环对一层的全部节点都进行遍历for(int i=left;i<=right;++i) {cur.push_back(i);dfs(cur,i+1,right,k);cur.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<int>cur;dfs(cur,1,n,k);return result;}
};困难：
这道题目的难点是需要把组合变成一个回溯的过程，迭代使用普通循环只是一个静态的组合枚举，需要给出的组合数个数固定才能使用普通的for循环嵌套。使用回溯需要设置好递归的参数，递归的结束条件和单层递归的操作，这里最重要的就是要把题目给出的所有已知数据全部变成正确的递归数据，组合的个数和组合的范围都需要正确的转化为递归的数据，这样设置完成后递归就能很快完成。
收获：
通过这道题目的练习了解到了组合情况的枚举使用回溯法的解法，通过回溯没想到可以这么简便的把所有情况都枚举出来，练习后对这类题目有了进一步的认识。
216.组合总和lll：
文档讲解：代码随想录|216.组合总和lll
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
状态：已做出
思路：
这道题目和上一道题目是鱼一类题目，这道题目限制在1和9之间的范围去找需要的数，那么设置的操作就比上一道题目简单，这里参数要比上一道题目设置的多，因为限制多，题目要求最后的组合总和需要打到目标值，所以需要把目标和添加为一个参数，还有一个参数是组合要求的个数，这两个参数就是判断递归结束的关键，当打到目标组合个数和总和后结束递归。这里递归单层循环都是从打到小遍历的，那么如果打到个数后继续向后遍历必定是大于这个目标值的，剪枝操作就是根据这个操作去设置的，但是我的代码并没有设置剪枝操作。
代码如下：
class Solution {
public:vector<vector<int>>result;void dfs(vector<int>&cur,int left,int k,int n,int sum) {//当要求个数和总和都达到要求后就把cur值存入result数组里if(sum==n && cur.size()==k) {result.push_back(cur);return;}//这里进行简要的剪枝操作，还有一个剪枝操作就是总和大于目标值后直接结束递归，这里没有设置这个剪枝操作if(cur.size()==k) return;//这里就和上一道题目的逻辑差不多，只是最后的固定值是9for(int i=left;i<=9;++i) {cur.push_back(i);sum+=i;dfs(cur,i+1,k,n,sum);cur.pop_back();sum-=i;}}vector<vector<int>> combinationSum3(int k, int n) {vector<int>cur;int sum=0;dfs(cur,1,k,n,sum);return result;}
};困难：
这道题目和上题类似，都是需要把问题转化为递归来解决，随意难点差不多，但这道题目的剪枝操作和上一题不同，因为这道题目是需要组合数的总和要打到目标值，所以剪枝文档给出的做法就是目标数总和大于等于目标值，随后的所有操作总和都一定大于目标值，直接减去既可。
收获：
这两道题目都是回溯的基础练习，通过两个类似的题目来对回溯有更加深刻的认识。
17.电话号码的字母组合：
文档讲解：代码随想录|17.电话号码的字母组合
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
状态：已做出
思路：
这道题目比起上面两道要复杂一点，因为你需要把数字和字母组合练习起来，所以需要设置一个全局变量来把所有数字和对应的字母组都保存起来，以便后面的操作。这里设置一个vector<string>的全局变量用来最保存最后的所有结果情况。这里设置的递归参数主要是一个int变量，用来记录此层遍历到的数字位置，一个就是题目所给出的包含需要判断的数字的字符串，最后一个参数则是当层所遍历后得到的数字对应的字母组合。递归结束条件是数字字母组数量打到目标个数后结束，这里单层for训话设置就是通过设置的int型参数找到对应字母的位置，把遍历对应的所有对应的字母并把此字母添加到第三个参数里去记录上，每次循环进行回溯操作，对字符串进行尾删操作。
代码如下：
class Solution {
public:vector<string>result;//这里就是使用一个string的vector容器来保存左右的数字对应的字母组合vector<string>a={"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void dfs(int cur,string get,string temp) {//这里当组合的个数等于数字的个数后直接结束递归if(temp.size()==get.size()) {result.push_back(temp);return;}//使用for循环进行回溯，这里是一层的宽度遍历for(int i=0;i<a[get[cur]-'1'].size(); ++i) {temp+=a[get[cur]-'1'][i];dfs(cur+1,get,temp);temp.pop_back();//回溯操作}}vector<string> letterCombinations(string digits) {string temp;result.clear();if(digits.size()==0) return result;dfs(0, digits,temp);return result;}
};困难：
这道题目的难点就是要设置一个变量来把数字和字母的对应关系给联系起来，并且要在递归中合理的去访问这个对应关系来找到合适的字母，其他的操作和上面两个题目没有太大区别，但是每层的for循环和前两个题目有所区别，因为题目要求是变遍历每一个数字所对应的所有字母，每个数字都是独立的，也就没有什么剪枝操作能优化遍历了。
收获：
通过上面三道相似的题目练习，对组合这类题目有了清晰放认识，使用回溯来解决组合枚举这类题目的确是非常好的做法，不用像迭代那样多层循环嵌套来解决，只用递归就可以实现这复杂的枚举过程。