Gen_Parentheses.java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private void backtrack(int openN, int closedN, int n, List<String> res, StringBuilder stack) {
        if(openN == closedN && openN == n){
            res.add(stack.toString());
            return;
        }

        if(openN < closedN){
            stack.append('(');
            backtrack(openN + 1, closedN, n, res, stack);
            stack.deleteCharAt(stack.length() - 1);
        }

        if(closedN < openN){
            stack.append(')');
            backtrack(openN, closedN + 1, n, res, stack);
            stack.deleteCharAt(stack.length() - 1);
        }

        public List<String> generateParenthesis(int n){
            List<String> res = new ArrayList<>();
            StringBuilder stack = new StringBuilder();
            backtrack(0, 0, n, res, stack);
            return res;
        }
    }
}