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时加入res
        vector<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;

    }
};