题意整理

• 给出n对括号，要求生成所有的由n对括号组成的合法组合。
• 合法的组合必须是对于每一个左括号，都有一个右括号与之对应。即所有左右括号能相互抵消掉。

方法一（暴力递归）

1.解题思路

• 利用递归遍历所有可能的组合。
• 对于每一个可能的组合，验证其是否合法，如果合法，则加入到res中。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    //记录最终的结果
    ArrayList<String> res=new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
        //利用递归遍历所有的情况
        generateAll(new char[n*2],0);
        return res;
    }
    
    private void generateAll(char[] arr,int index){
        if(index==arr.length){
            //如果合法，加入到res
            if(valid(arr)){
                res.add(String.valueOf(arr));
            }
        }
        else{
            //添加左括号
            arr[index]='(';
            generateAll(arr,index+1);
            //添加右括号
            arr[index]=')';
            generateAll(arr,index+1);
        }
    }
    
    //判断某个字符数组是否合法
    private boolean valid(char[] arr){
        int count=0;
        for(char c:arr){
            //如果是左括号加1
            if(c=='('){
                count++;
            }
            //如果是右括号减1
            else{
                count--;
            }
            //如果小于0，说明某个右括号没有对应的左括号抵消掉
            if(count<0){
                return false;
            }
        }
        //最终左右括号的数目必须相等
        return count==0;
    }
}

3.复杂度分析

• 时间复杂度：对于所有左右括号的组合，总共有$2^{2n}2^\{2n\}$个，每个组合都需要用valid来验证是否合法，valid函数的复杂度为$O(n)O(n)$，所以时间复杂度为$O(n\ast 2^{2n})O(n*2^\{2n\})$。
• 空间复杂度：递归栈的深度最多为$2\ast n2*n$，所以空间复杂度是$O(n)O(n)$。

方法二（剪枝）

1.解题思路

利用合法括号具备的特点，我们可以在递归过程中，直接排除掉某些不合法的情况。

• 当左括号数目小于n时，才添加左括号。
• 当左括号数目大于右括号时，才添加右括号。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    //记录最终的结果
    ArrayList<String> res=new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
        //利用递归遍历所有的情况
        dfs(n,n,new StringBuilder());
        return res;
    }
    
    private void dfs(int l,int r,StringBuilder sb){
        //添加完所有的左右括号
        if(l==0&&r==0){
            //将合法结果加入到res
            res.add(sb.toString());
            return;
        }
        //如果左括号未添加完
        if(l>0){
            //添加左括号
            sb.append("(");
            dfs(l-1,r,sb);
            sb.deleteCharAt(sb.length()-1);
        }
        //如果已添加的左括号多余右括号
        if(l<r){
            //添加右括号
            sb.append(")");
            dfs(l,r-1,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

3.复杂度分析

• 时间复杂度：取决于第n个卡特兰数，即$\frac{1}{n+1}\left(\genfrac{}{}{0px}{}{2n}{n}\right)\backslash frac\{1\}\{n+1\}\backslash tbinom\{2n\}\{n\}$，渐进于$\frac{4^n}{n\sqrt{n}}\backslash frac\{4^n\}\{n\backslash sqrt\{n\}\}$，所以时间复杂度为$O(\frac{4^n}{n\sqrt{n}})O(\backslash frac\{4^n\}\{n\backslash sqrt\{n\}\})$。
• 空间复杂度：递归栈的深度最多为$2\ast n2*n$，所以空间复杂度是$O(n)O(n)$。