题解 | #括号生成#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
     ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        dfs(0,0,"",n);
        return res;   
    }
    
    public void dfs(int left ,int right ,String temp,int n){
	    //左右括号都用完了，就加入结果
        if(left ==n && right ==n){
            res.add(temp);
            return;
        }
	  // 加入一个左括号
        if(left < n){
            dfs(left+1,right,temp+"(",n);
        }
	  //保证左括号出现的次数比右括号多时我们再使用右括号就一定能保证括号合法了
        if(right<n && left>right){
            dfs(left,right+1,temp+")",n);
        }
    }
}