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;
    }
    private void dfs(int n ,String s,int left, int right, ArrayList<String> result){
        if(left > n || right > n || right > left ){
            return;
            
        }
        if( left == n && right == n){
            result.add(s);
            return;
        }
        dfs(n,s + "(", left + 1, right,result);
        dfs(n,s + ")",left, right + 1,result);
    }
}