题解 | 括号生成

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    //一个很神奇的思路，字符串的一个前缀必须是左括号的数量大于右括号的数量，同时必须以左括号开始 右括号结束  
    ArrayList<String> res = new ArrayList<String> ();
    public void generateStr(int left,int right,StringBuilder str,int n){
        if(left == n && right == n){
            res.add(str.toString()); 
        }
        //增加左括号的情况
        if(left<n && left>=right){
            str.append('(');
            generateStr(left+1,right,str,n);
            // 一定要有回溯操作，比如，我现在是（（  我要去增加（）的场景，一定是先要吧目前左括号移除才能继续
            str.deleteCharAt(str.length()-1);

        }
        //增加右括号的情况
        if(right<n && left>=right){
            str.append(')');
            generateStr(left,right+1,str,n);
            str.deleteCharAt(str.length()-1);

        }
        return;

    }
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        StringBuilder substr = new StringBuilder();
        generateStr(0,0,substr,n);
        return res;
    }
}