LeetCode22 括号生成

题目描述

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

样例

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

算法分析

• 条件1 任意前缀(的数量大于等于)的数量
• 条件2 左右括号的总数量相等

满足上述两个条件就是有效括号

• dfs 递归
• 左括号， <n 可以任意填
• if(l < n) dfs(n, l+1, r, s + '(' );
• 右括号<n, 还要满足左括号>右括号
• if(r < l) dfs(n, l, r+1, s + ')' );

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

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 + ')' );  //r 要严格小于 l ，才能添加
    }

    public List<String> generateParenthesis(int n) {
        ans.clear();
        dfs(n,0,0,"");
        return ans;
    }
}