回溯算法详解：理论+基础类回溯题解_回溯法的理论基础

五：括号生成问题

这个问题也比较经典，题目的要求是让你生成所有可能的并且 有效的 括号组合。

对于括号问题，两个特性，请你一定记牢

1. 一个合法的括号左括号数量一定等于右括号的数量
2. 从左往右数一定是左括号先多，也就是不能先出现右括号

根据回溯算法的思路，本题给出了n，那么对于其每一种可能就有2*n个位置，也就是这道题就转化为了每个位置如何放置括号可以满足括号组合是合法的这样的问题

那么很显然，我们可以暴力穷举所有可能的组合，然后再从其中剔除掉不可能的组合即可。这里我们可以这样做，分别用left和right记录左右括号的数量，放置一个左括号，那么left就减一，放置一个右括号那么right就减一。

class Solution {
public:
    vector<string> ret;
    vector<string> generateParenthesis(int n) 
    {
        if(n==0)//特判
        {
            return ret;
        }
        string track;//一个组合
        back(track,n,n);
        return ret;
    }
    void back(string& track,int left,int right)
    {
        //从左往右一定是左括号多
        if(left>right)
            return;
        if(left<0 || right<0)//如果括号数大于3个，那么就结束递归，然后跑到pop_back处，删掉多余的括号
            return;
        //所有括号恰好用完时，满足
        if(left==0 && right==0)
        {
            ret.push_back(track);
            return;
        }

        //放左括号
        track.push_back('(');
        back(track,left-1,right);
        track.pop_back();
        //放右括号
        track.push_back(')');
        back(track,left,right-1);
        track.pop_back();
    }
};
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

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        vector<int> track;
        back(candidates,track,target);
        return ret;

    }
    void back(vector<int>& candidates,vector<int>& track,int target)
    {
        // sort(track.begin(),track.end());
        // if(ret.size()!=0)
        // {
        //     for(int i=0;i<ret.size();i++)
        //     {
        //         if(ret[i]==track)
        //             return;
        //     }
        // }

        int sum=accumulate(track.begin(),track.end(),0);
        if(sum==target)
        {
            ret.push_back(track);
            return;
        }
        if(sum>target)
            return;

        for(int i=0;i<candidates.size();i++)
        {

            track.push_back(candidates[i]);
            back(candidates,track,target);
            track.pop_back();
        }

    }
};
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

六：组合总和（点击跳转）

这个问题要我们找出数组中可以加和生成目标数的数字，一个数字可以无限次选取。基本框架不用多说，这里需要注意，如果只把框架写出来，它生成的这些数字是满足题意的，但是有一部分会重复，所以我们在把一个组合假如到返回结果之前，需要判断一下这个待加入的组合是否之前出现过，所以为了减少回溯次数，在开始就要将原数组排序好

class Solution {
public:
    vector<vector<int>> ret;//返回结果
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());//为了减少回溯次数，先排好序
        vector<int> track;//用于保存一个满足题意的组合
        back(candidates,track,target);
        return ret;

    }
    void back(vector<int>& candidates,vector<int>& track,int target)
    {
        int sum=accumulate(track.begin(),track.end(),0);//每次进入时，利用accumulate函数计算这个组合的数字之和是否达到了要求
        if(sum==target)//如果等于目标值，表明达到了要求
        {
            vector<int> judge(track);
            sort(judge.begin(),judge.end());//但是我们需要判断此时满足调节的这个组合之前是否出现过，所以要排好序进行判断（因为首先出现的那些情况一定是基准，是有序的）
            if(ret.size()!=0)
            {
                for(int i=0;i<ret.size();i++)
                {
                    if(ret[i]==judge)//一旦出现重复，不准加入
                        return;
                }
            }
            ret.push_back(track);//不重复的话，就作为一种选择加入
            return;
        }
        if(sum>target)//如果大于，直接不满足
            return;

        for(int i=0;i<candidates.size();i++)
        {

            track.push_back(candidates[i]);//做选择
            back(candidates,track,target);//回溯
            track.pop_back();//撤销选择
        }

    }
};
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

七：子集问题（点击跳转）

这道题比较有意思，因为他的决策树不是特别好找，关键就在于发现规律。
举个例子[1,2]的所有子集为：【[],[1],[2],[1,2]】，而[1,2,3]的子集为：【[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]】，大家有没有发现123的子集就是12的子集追加3，那么12的子集就是1的子集追加2，同时1的子集就是空集追加1，，因此其决策树为

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<int> track;
        back(nums,track,0);
        return ret;
    }

    void back(vector<int>& nums,vector<int>& track,int start)//注意start这个变量
    {
        ret.push_back(track);
        for(int i=start;i<nums.size();i++)//123的子集等12的子集追加3，12的子集等于1的子集追加2,1的子集等于空集追加1
        {
            track.push_back(nums[i]);
            back(nums,track,i+1);
            track.pop_back();
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22