题解 | #括号生成#TOP60

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> result = new ArrayList<String>();
        if(n< 1){
            return result;
        }
        if( n == 1){
            result.add("()");
            return result;
        }
        
        dfs(n,"",0,0,result);
        return result;
    }
    //left 和 right 代表有多少对括号了
    private void dfs(int n ,String s,int left, int right, ArrayList<String> result){
        //边界条件  例如 ()) 是不符合要求的，或者 ()()(() 有右括号，左括号肯定要对应数量
        if(right > left || left > n || right > n){
            return;
        }
        //终止条件
        if(left == n && right == n){
            result.add(s);
            return;   
        }
        dfs(n, s + "(" , left + 1, right,result);
        dfs(n , s + ")" , left, right + 1,result);
    }
}