leetcode22.括号生成

题目链接：力扣

数字 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<

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<