class Solution {
    public List<String> generateParenthesis(int n) {
        ArrayList<String> parens = new ArrayList<String>();

        auxGenerateParen(parens, n, 0, 0, new StringBuilder());
        return parens;
    }

    private static void auxGenerateParen(ArrayList<String> parens,int n, int left, int right, StringBuilder str){
        if(right == n){
            parens.add(str.toString());
            return;
        }
        if(left < n){
            auxGenerateParen(parens, n, ++left, right, str.append("("));
        }
        if(right < left && right < n){
            auxGenerateParen(parens, n, left, ++right, str.append(")"));
        }




    }
}