Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

递归，记录左右括号还剩几个，同时检测当前是否合法

public class Solution {
    //Time: O(2^n)  
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>();
        generate("", n, n, res);
        return res;
    }
    
    private void generate(String cur, int left, int right, ArrayList<String> res) {
        if (left > right || left < 0 || right < 0) {
            return;
        }
        
        if (left == 0 && right == 0) {
            res.add(cur);
            return;
        }
        
        generate(cur + "(", left - 1, right, res);
        generate(cur + ")", left, right - 1, res);
    }
}