leetcode22. 括号生成(C++|回溯|剪枝)

题目链接：力扣

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8

这道题目花了我大概两个多小时，快吐了。代码10分钟左右就写好了，因为和全排列的方式很像，几乎一样，但是我困在哪里了啊？就是一个bug，晕。我string类型的一个数组居然调用了size()方法，导致数组越界，出现AddressSanitizer:DEADLYSIGNAL 错误。排查了两个多小时，越是找不到就越想找。最后上了个厕所之后，才发现，呜呜呜。不过在睡觉之前找到bug还是很开心的，加油！

言归正传，这道题目和全排列很像，因为数据n<8，所以采用暴力回溯是没有问题的，这里还采用了剪枝，不过只利用了一个性质，即左右括号的数量一定相等（第一条提交记录）。当然，还有另一个性质可以利用，即左括号的剩余数量一定要少于右括号的剩余数量，反过来就是左括号的使用数量一定要大于等于右括号的使用数量，即下文中的left>=right（第二条提交记录），想一想，为什么呢？

看了题解，发现也有用动态规划解的，那个就很厉害了，我还没有仔细看。

先贴上我的代码吧！

这个复杂度没有仔细研究，后续补上，我要睡觉了。

class Solution {
public:
    vector res;
    string path;
    vector generateParenthesis(int n) {
        brace(n,0,0);
        return res;
    }

    bool isCorrect(string brace){
        int left=0;
        for(int i=0;i0){
                    left--;
                }else{
                    return false;
                }
            }
        }
        return true;//在后续代码中已经确保了左右括号相等
    }
    void brace(int n,int left,int right){
        
        //左右括号不相等
        if(left>n||right>n){
            return;
        }
        // cout< 
代码2 
class Solution {
public:
    vector res;
    string path;
    vector generateParenthesis(int n) {
        brace(n,0,0);
        return res;
    }

    bool isCorrect(string brace){
        int left=0;
        for(int i=0;i0){
                    left--;
                }else{
                    return false;
                }
            }
        }
        return true;//在后续代码中已经确保了左右括号相等
    }
    void brace(int n,int left,int right){
        
        //左右括号不相等，左括号使用数量大于等于右括号使用数量才可以，否则不合法
        if(left>n||right>n||right>left){
            return;
        }
        // cout<