Recursive Solution - Generate Parentheses *

It can be resolved by classic recursive approach. The idea is to keep both left parenthesis and right parenthesis to be n. The advantage here is that String operations like + does generate a new reference each time, so we don't need to worry about cleaning after each add.

Basic principle is to add left, update left amount, and then add right, update right amount, by recursive calls. If both are n, add result, if only left reach first (guaranteed since call recursive first than right), only recursive call right, and left should always bigger than right, reason as above.

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> results = new ArrayList<String>();
        generateParenthesisOps(n, 0, 0, "", results);
        return results;
    }
   
    private void generateParenthesisOps(int n, int left, int right, String s, ArrayList<String> results){
        if(left < right){
            return;
        }
        if(left == n && right == n){
            results.add(s);
            return;
        }
        if(left == n){
            generateParenthesisOps(n, left, right + 1, s+")", results);
            return;
        }
        generateParenthesisOps(n, left + 1, right, s + "(", results);
        generateParenthesisOps(n, left, right + 1, s + ")", results);
    }
}