题目描述

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

样例

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

算法分析

• 1、dfs(int n,int l,int r,String s)：n表示最多有n个左括号和右括号，l表示左括号的个数，r表示右括号的个数，s表示当前的序列
• 2、若l < n，左括号的个数小于n，则可以在当前序列后面拼接左括号
• 3、若r < l，右括号的个数小于左括号的个数，则可以在当前序列后面拼接右括号

时间复杂度 $O(C_{2n}^n)$

直接生成合法的序列一定满足右括号的个数总是小于等于左括号的个数，是一个典型的卡特兰数问题，卡特兰数的时间复杂度是$O(\frac{C_{2n}^n }{n + 1})$

Java 代码

class Solution {
    static List<String> ans = new ArrayList<String>();
    static void dfs(int n,int l,int r,String s)
    {
        if(l == r && l == n)
        {
            ans.add(s);
            return ;
        }
        if(l < n) dfs(n,l + 1,r,s + "(");
        if(r < l) dfs(n,l,r + 1,s + ")");
    }
    public List<String> generateParenthesis(int n) {
        ans.clear();
        dfs(n,0,0,"");
        return ans;
    }
}