题解 | #括号生成#

思路：

题目的主要信息：

• 求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行
• 需要输出所有的结果

方法一：暴力构造+栈验证
具体做法：
首先构造一个"(((((((......))))))"形式的字符串，然后调用STL的next_permutation函数遍历其每一个排列组合，并验证其是否合法，如果合法则可以加入返回的vector中。
验证合法时，使用辅助栈，遇到左括号则入栈，遇到右括号则弹出一个栈中内容，若是栈为空的时候遇到了右括号，则没有左括号来匹配，即非法。

class Solution {
public:
    bool isValid(string str){ //验证括号是否合法
        stack<char> s; //栈中只存左括号
        for(int i = 0; i < str.length(); i++){
            if(s.empty() && str[i]==')')  //空栈遇到右括号，不合法
                return false;
            if(str[i] == ')')  //遇到右括号弹出一个左括号
                s.pop();
            else 
                s.push(str[i]); //加入左括号
        } 
        return true;
    }
    vector<string> generateParenthesis(int n) {
        string str1(n, '(');
        string str2(n, ')');
        string str = str1 + str2;  //将所有括号写入str
        vector<string> strs;
        do{
            if(isValid(str))  //合法括号入vector
              strs.push_back(str);
        }while(next_permutation(str.begin(), str.end())); //生成下一排列组合
        return strs;
    }
};

复杂度分析：

• 时间复杂度：，next_permutation是一个全排列，加上每次都验证2n长度的字符串
• 空间复杂度：，辅助栈和构造字符串时使用的空间

方法二：递归+余量构造法
具体做法：
全部构造的方法，构造了很多不必要的字符串，导致运算量陡增，我们可以用余量构造法：
一开始左右括号数剩余都是n，总括号数剩余2n，构造一个就用掉一个相应的括号，只有在括号都有余量的时候才能继续构造，而右括号还需要限制在余量比左括号多的时候才能继续构造。
每次构造采用递归的方式，构造了括号，把相应的括号数量减1送入子问题中进行递归。
这种方法也叫枝剪法：修剪递归树多余的部分。

class Solution {
public:
    void recursion(int left, int right, int count, string s, vector<string>& res){
        if(count == 0){
            res.push_back(s);
            return;
        }
        else if(left > 0) //左边还可以放
            recursion(left - 1, right, count - 1, s + "(", res);
        if(right > left) //右边也可以
            recursion(left, right - 1, count - 1, s + ")", res);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        recursion(n, n, 2 * n, "", res); //左右括号及总括号数余量放入递归
        return res;
    }
};

复杂度分析：

• 时间复杂度：，复杂度取决于有多少个合法括号组合，这是第n个卡特兰数，由渐近界定的
• 空间复杂度：，递归栈最大空间，其中res数组是返回时必须要的，不算额外空间