代码随想录算法训练营回溯算法Day-22 | 理论基础、77. 组合、216.组合总和III、17.电话号码的字母组合

理论基础回溯与递归的关系回溯是递归的副产品有递归就会有回溯本质回溯的本质就是穷举并不是高效的算法因为有些问题只能用穷举法解决回溯解决的问题1. 组合问题N个数里面按一定规则找出k个数的集合2. 切割问题一个字符串按一定规则有几种切割方式3. 子集问题一个N个数的集合里有多少符合条件的子集4. 排列问题N个数按一定规则全排列有几种排列方式5. 棋盘问题N皇后解数独等等理解回溯所有回溯法解决的问题都可以抽象成树状结构回溯法解决的都是在集合中查找子集所以集合的大小构成树的宽度递归的层数构成树的深度由于递归都有终止条件所以一定是有限高的N叉树。回溯函数三部曲1.返回类型、函数名和参数列表void backtracking(参数)//先写逻辑需要什么参数再填什么参数2.回溯函数终止条件if (终止条件) { 存放结果; return; }3.回溯遍历过程注上图集合大小与孩子数量相等回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 }77. 组合本题要解决从1~n这个集合中选出大小为k的无序子集合。回溯函数返回值和参数列表返回值void参数列表传入n、k、startIndex开始索引也就是防止重复选择需要递增的一个开始遍历的起始值函数作用是从数字startIndex开始逐个尝试选择数字加入path直到凑够k个数字把组合存入result。终止条件设置全局变量path和result当path大小为k时说明找到了一个结果直接执行存入result的操作然后return递归逻辑如果不满足终止条件就按照开始索引开始遍历集合每一次循环执行先往path加入i再递归n,k,i1然后poo_back()删掉刚加入的最后一个元素执行下一个循环因为此时就会加入i1变成了一个新的集合以此来得到所有可能的组合具象化函数功能初始path是空那么调用4,2,1就会实现往result中存入所有组合如果path中有个1因为2i1i1所以1已经被加入到path中去了调用4,2,2就会实现往result存入1,21,31,4这三个结果执行完1,4后会pop掉4留下1返回到第一层递归又该执行pop操作了所以又pop掉1path又是空了开始进行下一个循环i2。class Solution { public: vectorint path; vectorvectorint result; void backtracking(int n, int k, int startIndex){ if(path.size()k){ result.push_back(path); return; } for(int i startIndex;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 result; } };剪枝操作比如C4,4当i2时其实能选的元素只有3,4了最多只能选3个了所以遍历2其实是没必要的这就是剪枝操作的由来由于每次for循环其实都是对应一个子孩子所以现在不需要遍历每个子孩子比如1,2,3,4不需要遍历2,3,4所以就要从for循环的范围做文章。考虑现在path的大小path.size()如果需要k个所以剩余需要选取的元素个数为k-path.size()所以对应到索引i就是最多在n-(k-path.size())1的位置开始遍历能刚好取完k个元素再大就取不完k个元素了所以只需要把for循环中的in改为in-(k-path.size())1即可。class Solution { public: vectorint path; vectorvectorint result; void backtracking(int n, int k, int startIndex){ if(path.size()k){ result.push_back(path); return; } for(int i startIndex;in-(k-path.size())1;i){ path.push_back(i); backtracking(n,k,i1); path.pop_back(); } return; } vectorvectorint combine(int n, int k) { backtracking(n, k, 1); return result; } };216.组合总和III本题理解了上一题后很简单自己A出来了激动。其实就是求C(9,k)然后多一个判断条件也就是path之和是否为n是n的话把path加入result否则不加入即可不多解释直接上代码。注意if里面sumn要返回sum!n也要返回class Solution { public: vectorint path; vectorvectorint result; void backtracking(int k, int n, int startIndex) { if(path.size()k){ int sum 0; for(auto i:path){ sumi; } if(sum n){ result.push_back(path); return; } return; } for(int istartIndex;i9-(k-path.size())1;i){ path.push_back(i); backtracking(k,n,i1); path.pop_back(); } } vectorvectorint combinationSum3(int k, int n) { backtracking(k, n, 1); return result; } };17.电话号码的字母组合这个题重点在于不是传统的组合问题传统的组合问题是从同一个集合中选取元素组合本题是从不同数字对应的字母组合中选取元素组合。其实就是在传统组合的基础上把原始的单个集合变成每次不同的集合。传统组合问题通过startIndex每次调用时递增使得每次选元素时是从原集合的子集合例如第一次1234start1第二次234start1第三次34......集合范围抽象到代码里就是for循环的索引范围字母组合问题通过数字索引index每次递增但递增后是从数字-字符表中选取新的集合index2时集合为abcindex3时集合为def用一个数组存起来每次for循环之前先找到这个集合所以代码也改的不多class Solution { public: const string stringMap[10]{ , , abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 }; string path; vectorstring result; void backtracking(const string digits,int index){ if(indexdigits.size()){ result.push_back(path); return; } int num digits[index]-0; string str stringMap[num]; for(int i0;istr.size();i){ path.push_back(str[i]); backtracking(digits, index1); path.pop_back(); } } vectorstring letterCombinations(string digits) { backtracking(digits, 0); return result; } };