题解 | #括号生成#

import java.util.*;


public class Solution {
   int left,right,n1;
   ArrayList<String> ret ;
   StringBuilder path;
    public ArrayList<String> generateParenthesis (int n) {
        //有效括号：左括号数量等于右括号，
        //从头开始的任意一个子串左括号数量>=右括号
        ret = new ArrayList<>();
        path = new StringBuilder();
        n1 = n;
        left=right=0;
        dfs();
        return ret;
    }

    public void dfs(){
        if(right==n1){
            ret.add(path.toString());
            return;
        }
        //在进行括号选择时有两种情况
        if(left<n1){
            //添加左括号
            path.append('(');
            left++;
            //进入下一层
            dfs();
            //回溯
            path.deleteCharAt(path.length()-1);
            left--;

        }
        //添加右括号
        if(right<left){
            path.append(')');
            right++;
            //进入下一层
            dfs();
            //回溯
            path.deleteCharAt(path.length()-1);
            right--;

        }
    }


}