1.回溯总结

主要参考下面的题目，代码随想，还有labuladong，这个类型的主要思路就是，找

到结束条件，然后就是进行选择，放入之后，就再次进行放出

1
2
3
4
5
6
7
8
9
10
11
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

包含下面几个题目

46全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> res;
    vector<bool> st;
    vector<vector<int>> permute(vector<int>& nums) {
        st=vector<bool> (nums.size());
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int> &nums,int u){
        if(u==nums.size()){
            ans.push_back(res);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (!st[i]){
                st[i]=true;
                res.push_back(nums[i]);
                dfs(nums,u+1);
                res.pop_back();
                st[i]=false;
            }
        }
    }
};

首先还是使用ans进行保存，使用st进行验证，u代表成功的个数，当为n，就是可以进行添加，从0开始进行访问所有的值

51.N皇后

这个题目就是进行求解，他的check条件就是列上没有，，斜线上没有，斜线就是当前的点（x-1，y-1），（x-1，y+1），检查这些值有没有，没有就放，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> res;
    vector<vector<string>> solveNQueens(int n) {
        res=vector<string>(n,string(n,'.'));
        dfs(n,0);
        return ans;
    }
    void dfs(int n,int u){
        if(n==u){
            ans.push_back(res);
            return ;
        }
        for (int i = 0; i < n; ++i) {
            if(isok(u,i)){
                res[u][i]='Q';
                dfs(n,u+1);
                res[u][i]='.';
            }
        }
    }
bool isok(int u,int i){
        //统计每一个竖起来的
        //统计左上还有右下
        int n=res.size();
    for (int j = 0; j <=u; ++j) {
        if(res[j][i]=='Q')return false;
    }
    //45°检查
    for (int j = u-1,k=i-1; j>=0&&k>=0 ; j--,k--) {
        if(res[j][k]=='Q')return false;

    }
    for (int j = u-1,k=i+1; j>=0&&k<n ; j--,k++) {
        if(res[j][k]=='Q')return false;

    }
    return true;
    }
};

112路径总和

从根节点开始寻找，两种dfs方式，一种就是在for循环里面进行回溯，还有一种在最开始进行回溯。

这个就是在里面进行回溯，因为是直接开始减的，所以，不需要把target还原

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root)return false;
        return dfs(root,targetSum-root->val);
    }
    bool dfs(TreeNode* root,int target){
        if (target==0&&!root->left&&!root->right){
            return true;
        }
//        if (target<0)return false;
        if(root->left){
            bool left= dfs(root->left,target-root->left->val);
            if (left)return true;
        }
        if(root->right){
            if(dfs(root->right,target-root->right->val)){
                return true;
            }
        }
        return false;
    }
};

140.单词拆分

这个题目还是回溯，本质就是对i从u开始，进行截取，然后，看是不是在指点里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    unordered_map<string,int> rec;
    vector<string> ans;
    string path;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for(auto word:wordDict){
            rec[word]++;
        }
        dfs(s,0);
        return ans;
    }
    void dfs(string s,int u){
        if(u==s.size()){
            path.pop_back();
            //排除末尾
            ans.push_back(path);
            path+=" ";
            return;
        }
        if(u>s.size()){
            return;
        }
        for (int i = u; i <s.size() ; ++i) {
            auto t=s.substr(u,i-u+1);
            if(rec.find(t)!=rec.end()){
                auto x=path;
                path+=t+" ";
                dfs(s,i+1);
                path=x;
            }
        }
    }
};

17.电话组合

还不是组合一样，放入字符串里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> ans;
    string strs[10] = {
            "", "", "abc", "def",
            "ghi", "jkl", "mno",
            "pqrs", "tuv", "wxyz",
    };
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits.empty())return ans;
        dfs(digits,0);
        return ans;

    }
    void dfs(string digits,int u){
        if(u==digits.size()){
            ans.push_back(path);
            return;
        }
        if(u>digits.size())return;
        int n=digits[u]-'0';
        for (int i = 0; i < strs[n].size(); ++i) {
            path.push_back(strs[n][i]);
            dfs(digits,u+1);
            path.pop_back();
        }
    }
};

22.括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<string> ans;
    string path;
    unordered_map<char,int> rec;
    vector<string> generateParenthesis(int n) {

        dfs(n,0);
        return ans;

    }
    void dfs(int n,int u){
        if(u==2*n){
            ans.push_back(path);
            return;
        }
//        cout<<path<<" ";
        if(rec.find('(')==rec.end()||rec['(']<n){
            path+='(';
            rec['(']++;
            dfs(n,u+1);
            path.pop_back();
            rec['(']--;
        }
        if (rec.find(')')==rec.end()||rec[')']<rec['(']){
            path+=')';
            rec[')']++;
            dfs(n,u+1);
            path.pop_back();
            rec[')']--;
        }

    }
};


两个剪纸，一个是长度都是n，括号，还有一个就是右括号小于左的

39.组合总和

这个就是组合数，使用i到u进行遍历，然后还有一个就是，直接从i开始，不是i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return ans;
    }
    void dfs(vector<int> &nums,int u,int index){
        if (u==0){
            ans.push_back(path);
            return;
        }
        if (index==nums.size())return;
        if(u<0)return;
        for (int i = index; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            dfs(nums,u-nums[i],i);
            path.pop_back();
        }

    }
};

这个就是从i即系开始，可以重复使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    
    vector<vector<int>> combinationSum(vector<int>& c, int target) {
            dfs(c,0,target);
            return ans;
    }

    void dfs(vector<int>& c,int u,int target ){
        // u代表当前循环到哪一个了数字呢
        // 考虑边界
        if(target==0){
            ans.push_back(path);
            return;
        }
        if(u==c.size()){
            return;
            // 直接返回
        }
        // 接下来就是放入放出
        for(int i=0;i*c[u]<=target;i++){

            dfs(c,u+1,target-i*c[u]);
            path.push_back(c[u]);


            // 这是选择加入一个后，再对后面的进行加入
            // target-i*c[u]是加入当前的次数，u+1是下一个值
             // 回复现场
             
            
        }
        for(int i=0;i*c[u]<=target;i++){
            path.pop_back();
        }
        
    }
};

这个代码很不错，因为是先dfs然后再push，为什么了，因为先dfs，代表选0个当前的，之后放入一个，就是选了一个dfs，而且是在dfs之后选择下一个值，而且，target因为是没有变，所以直接减去i*cu

698.划分k个相等的子集

首先的先决条件就是sum数组的和可以整除k，而且最后一个数，一定小于平均数。之后就是进行回溯，代码思路，使用dfs(nums,avg,k,u)

含义就是当avg为0的时候，可以进行k-1（表示又有一组满足了，然后u从开始进行寻找，avg再次恢复到初始值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<vector<int>> ans;
    vector<int>path;
    vector<bool> st;
    int t;
    int avg;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
         auto sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%k!=0)return false;
        st=vector<bool>(nums.size(),false);
        int target=sum/k;
        if (nums.back()>target)return false;
//
        t=k;
        avg=target;
        sort(nums.begin(),nums.end());
        return dfs(nums,target,0,0);


    }
    bool  dfs(vector<int> &nums,int target,int index,int u){
        if(u==t)return true;
//        cout<<u;
        if(target==0)return dfs(nums,avg,0,u+1);
//        if(target<0)return false;
        for (int i = index; i < nums.size(); ++i) {
            if(!st[i]&&target-nums[i]>=0){
                st[i]=true;
//                path.push_back(nums[i]);
                if(dfs(nums,target-nums[i],i+1,u)){
                    return true;
                }
                st[i]=false;
//                path.pop_back();
                    //排好序了的,如果当前都没办法减少到0,后面就不可能
                if (target==avg)return false;
            }
        }
        return false;
    }

};

if (target==avg)return false;重要剪纸，当表示值不变还是avg，就表示后面更不可能进行减少值，因为后面的都比当前值大，target会一直不变，所以不能选择，直接失败

77.组合数

组合数，就是进行选择，首先进行排序，i到u开始，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> rec;
    vector<bool>st;
    vector<vector<int>> combine(int n, int k) {
        st=vector<bool> (n+1,false);
        dfs(n,k,1);
        return ans;
    }
    void dfs(int n,int k,int u){
        if(!k){
            ans.push_back(rec);
            return;
        }

        for (int i = u; i < n+1; ++i) {
            rec.push_back(i);
            dfs(n,k-1,i+1);
            rec.pop_back();
        }
    }
};

78,幂集

就是返回所有的选择,直接在上面的进行手动设置k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> rec;
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i <=nums.size(); ++i) {
            dfs(nums,i,0);
        }
        return ans;
    }
    void dfs(vector<int> &nums,int k,int u){
        if(!k){
            ans.push_back(rec);
            return;
        }

        for (int i = u; i < nums.size(); ++i) {
            rec.push_back(nums[i]);
            dfs(nums,k-1,i+1);
            rec.pop_back();
        }
    }
};

40.组合综合

进行筛选,而且不能含有重复的,首先进行选择就是i到u,去重就是要使用那个continue,与前面相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return ans;
    }
    void dfs(vector<int> &nums,int target,int u){
        if(target==0){
            ans.push_back(path);
            return;
        }
        if(u>=nums.size())return;
//
//        cout<<target<<"  ";
        for (int i = u; i < nums.size(); ++i) {
            if(nums[i]>target)return;
            if (i>u&&nums[i]==nums[i-1])continue;
            path.push_back(nums[i]);
            dfs(nums,target-nums[i],i+1);
            path.pop_back();
//            rec[nums[i]]=1;
        }
    }
};

if (i>u&&nums[i]==nums[i-1])continue;去重代码,不需要使用st,来表示,因为后面都是没有访问的

216.组合综合

还是之前一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> path;
vector<vector<int>> ans;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1,k,n);
        return ans;
    }
    void dfs(int start,int k,int n){
        if(!k){
            if(!n)ans.push_back(path);
        }else if(k){
            // 说明还有字数需要
            for(int i=start;i<=9;i++){
                if(n>=i){
                    path.push_back(i);
                    dfs(i+1,k-1,n-i);
                    path.pop_back();
                }
            }
        }
    
    }
};

131.分割回文串

还是之前一样,check条件就是是不是会问,如果是true,直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return ans;
    }
    void dfs(string s,int u){
        if(u==s.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = u; i < s.size(); ++i) {
            auto x=s.substr(u,i-u+1);
            if(is_ok(x)){
                path.push_back(x);
                dfs(s,i+1);
                path.pop_back();
            }
        }
    }

    bool is_ok(string s){
        auto x=s;
        reverse(s.begin(),s.end());
        return x==s;
    }
};

93复原ip地址

这个首先是对于0,直接继续,而且,一共只有4个小数点,最后一个在加入的时候去除,之后就是普通的回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int start;
    int end;
    vector<string> ans;
    string path;
    vector<string> restoreIpAddresses(string s) {
        start=0,end=255;
        dfs(s,4,0);
        return ans;
    }
    void dfs(string s,int times,int u){
        //不出现011
        //只有3个小数点可以进行加入
        if (!times&&u==s.size()){
            path.pop_back();
            ans.push_back(path);
            return;
        }
        if (times<0)return;
        if(u>=s.size())return;
        if(s[u]=='0'){
            path+="0.";
            dfs(s,times-1,u+1);
            return ;
        }else{
            for (int i = u; i < s.size(); ++i) {
                if (i-u+1>3)return;
                auto x=s.substr(u,i-u+1);

                auto t= stoi(x);
                if(t<=255){
                    auto back=path;
                    path+=x+".";
                    dfs(s,times-1,i+1);
                    path=back;
                }
            }
        }


    }
};

对于签到0的优化方法就是把循环的下一位变成u+1,不是s.size

1
2
3
4
int n=u+1;
        if(s[u]!='0')n=s.size();
       
            for (int i = u; i < n; ++i) {

90子集

这个就是进行去重,直接看是不是相等,然后continue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i <=nums.size(); ++i) {
            dfs(nums,i,0);
        }
        return  ans;

    }
    void dfs(vector<int> &nums,int n,int u){
        if(n==0){
            ans.push_back(path);
            return;
        }
        if(u>=nums.size())return;
        if(n<0)return;
        for (int i =u; i < nums.size(); ++i) {
            if(i>u&&nums[i]==nums[i-1])continue;
            path.push_back(nums[i]);
            dfs(nums,n-1,i+1);
            path.pop_back();
        }
    }
};

因为都是排序了的,后面一定没有访问,所以不用st

47全排列

进行去重,这个就是需要st数组,因为从是排列,而且需要进行去重,所以是从0开始的,需要st

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
// 这题的意思就是要融合，消去2个112
// 去重使用三个数之和的方法，是不是前面一个相同，相同就跳过了
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        path= vector<int>(nums.size());
        st= vector<bool>(nums.size());
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int>& nums,int u ){
        if(u==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(!st[i]){
            if(i&&nums[i-1]==nums[i]&&!st[i-1])continue;
            // 前面一个还没有使用，那就用前面那个1
                st[i] = true;
                path[u] = nums[i];
                dfs(nums, u + 1);
                st[i] = false;
            }
        }

    }
};

491递增子序列

因为没有排序,不能排序,所以只能使用set来进行作为

本人思路,就是对所有n的n从2到size进行遍历,然后加进去,使用set去除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    set<vector<int>> s;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        for (int i = 2; i <=nums.size(); ++i) {
            dfs(nums,i,0);
        }
        return ans;
    }
    void dfs(vector<int>& nums,int n,int u){
        if(n==0){
            if(s.find(path)==s.end()){
                ans.push_back(path);
                s.insert(path);
            }

            return;
        }
        if(u==nums.size())return;
        for (int i = u; i <nums.size() ; ++i) {
            if(path.empty()||nums[i]>=path.back()){
                path.push_back(nums[i]);
                dfs(nums,n-1,i+1);
                path.pop_back();
            }

        }
    }
};

2.小结

上面的几个经典题目,一个去重,前面相等直接跳过

1
if(i>u&&num[i]==num[i-1])continue

第二个就是前导0的问题,一般是只能用做单独的0,那么距离就是u+1

1
2
3
int n=s.size();
if(s[i]=='0')n=u+1:
for(int i=u;i<n;i++)

第三个就是排列组合,排列的话就是从0开始,设置st数组.

组合的就是从u开始,去重和上面是一样的