day-24 代码随想录算法训练营（19）回溯part01

77.组合

思路一：回溯相当于枚举，所以我们遍历1-n的每一个数字，然后在遍历第i位的同时递归出第i+1~n位的组合结果，跟树的形式相似。

•  如上图所示，当长度为k时，即退出递归
• 可对遍历到第i位以及剩下位数与k进行比较进行一个剪枝（比如遍历到4时，4后面没有数字，不能组成个数为2的组合）

class Solution {
public:vector<vector<int>>res;void judge(int n,int index,int k,vector<int>&mid){if(mid.size()==k){res.push_back(mid);return;}for(int i=index;i<=n-(k-mid.size())+1;i++){mid.push_back(i);judge(n,i+1,k,mid);mid.pop_back(); //回溯，不回溯的话无法继续往下}}vector<vector<int>> combine(int n, int k) {//思路：遍历1-n为index，然后传入进行第k-index-1的组合，使用中间vector保存，当vector的size==k时加入resvector<int>mid;judge(n,1,k,mid);return res;}
};

216.组合总和III

分析：和上一题如出一辙，只是多加了一个判断总和，不过数字固定到1-9

class Solution {
public:vector<vector<int>>res;vector<int>mid;void backtrace(int k,int n,int sum,int startIndex){if(sum>n || mid.size()>k)return;if(sum==n && mid.size()==k){res.push_back(mid);return;}for(int i=startIndex;i<=9-(k-mid.size())+1;i++){sum+=i;mid.push_back(i);backtrace(k,n,sum,i+1);mid.pop_back();sum-=i;}}vector<vector<int>> combinationSum3(int k, int n) {//思路：和77题如出一辙backtrace(k,n,0,1);return res;}
};

17.电话号码的字母总和

画图分析：

 思路一：首先横向递归，对每一个位置的字符串数组进行递归遍历

            其次在递归遍历之前，对该位置的字符串数组进行遍历添加

            在递归遍历数组结束之后，需要回溯删除本数组添加的字符，以便于回溯到上一数组

class Solution {
public:vector<string>dists={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string>res;void backtrace(string digits,int start,string&mid){if(start==digits.size()){//递归遍历终点res.push_back(mid);return;}for(int i=0;i<dists[digits[start]-'0'].size();i++){//纵向遍历char midC=dists[digits[start]-'0'][i];mid.push_back(midC);backtrace(digits,start+1,mid);//横向递归遍历mid.pop_back();//回溯}}vector<string> letterCombinations(string digits) {if(digits.size()==0) return res;//极端情况string mid;backtrace(digits,0,mid);return res;}
};

131.分割回文串

思路：先使用for循环横向遍历，从每一个点截取，并且判断当前截取的字符串 i 是否为回文串

           1.当属于回文串时，把当前字符串加入数组，并且递归往下，从下一个字符开始再次使用for循环横向遍历，判断是否是回文字符

           2.当不属于回文串时，直接返回

 注意终止条件：当在递归过程中开始截取的位置startIndex大于等于原字符串的长度时，表示已经递归到了尽头

class Solution {
public:vector<vector<string>> res;vector<string>mid;bool judgeP(const string& s,int start,int end){int left=start,right=end;while(left<right){if(s[left++]!=s[right--])return false;}return true;}void backtrace(string s,int startIndex){if(startIndex>=s.size()){res.push_back(mid);return;}for(int i=startIndex;i<s.size();i++){if(judgeP(s,startIndex,i)){//判断当前区间内的字符是否回文串string str=s.substr(startIndex,i-startIndex+1);mid.push_back(str);}else//不是回文，跳过continue;backtrace(s,i+1);//寻找i=1为起始位置的子串mid.pop_back();//回溯}}vector<vector<string>> partition(string s) {//首先需要一个函数判断出来的字符是否回文串//思路：递归从0开始分割判断backtrace(s,0);return res;}
};