题解 | #括号生成#

题目主要信息:

• 求n对括号的所有合法组合，输出顺序不定
• 合法组合即每个右括号都能在左边有与之一一对应的左括号

具体思路:

相当于一共n个左括号和n个右括号，可以给我们使用。如果使用了一个左括号以后，那么还剩下n-1个左括号和n个右括号，也是将这些括号连接成一个字符串，就相当于是原问题的子问题，因此我们使用递归。但是这样递归不能保证括号一定合法，因此只有小括号，那只要左括号出现的次数比右括号多时我们再使用右括号就一定能保证括号合法了。

• 终止条件： 左右括号都使用了n个，将结果加入数组。
• 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
• 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。

具体过程可以参考如下图示：

代码实现:

class Solution {
public:
    void recursion(int left, int right, string temp, vector<string> &res, int n){
        if(left == n && right == n){ //左右括号都用完了，就加入结果
            res.push_back(temp);
            return;
        }
        if(left < n) //使用一次左括号
            recursion(left + 1, right, temp + "(", res, n);
        if(right < n && left > right) //使用右括号个数必须少于左括号
            recursion(left, right + 1, temp + ")", res, n);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> res; //记录结果
        string temp; //记录每次组装的字符串
        recursion(0, 0, temp, res, n); //递归
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，该递归最坏情况每个位置都可能出现左右两种括号，因此为$O(2^n)O(2^n)$
• 空间复杂度：$O(n)O(n)$，递归栈最大深度