题目描述

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

样例

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

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

限制

• 1 <= n <= 8

算法1

(暴力枚举，合法性判断) $O(n2^{2n})$

生成所有的括号序列，然后用栈逐个检查合法性。

时间复杂度

生成所有括号序列的时间复杂度 $O(2^{2n})$，检查的时间复杂度是 $O(n)$，故总时间复杂度是 $O(n2^{2n})$。

C++代码不再赘述

算法2

(直接生成合法的括号序列) $O(C_{2n}^{n})$

1. 使用递归。
2. 每次可以放置左括号的条件是当前左括号的数目不超过 $n$。
3. 每次可以放置右括号的条件是当前右括号的数目不超过左括号的数目。

时间复杂度

• 时间复杂度就是答案的个数，乘上保存答案的 $O(n)$ 计算量，该问题是经典的卡特兰数。
• 总时间复杂度为 $O(\frac{1}{n+1}C_{2n}^{n}) = O(C_{2n}^n)$。

C++ 代码：

class Solution {
public:
    vector<string> res;

    void solve(int l, int r, int n, string cur) {
        if (l == n && r == n) {
            res.push_back(cur);
            return;
        }

        if (l < n)
            solve(l + 1, r, n, cur + "(");

        if (r < l)
            solve(l, r + 1, n, cur + ")");
    }

    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return res;

        solve(0, 0, n, "");

        return res;
    }
};