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:

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

Another recursion problem. Add "(" to the string, and decrease the total "(" number, when the number of left parenthesis and right parenthesis left both equal 0, add the string to rst list. If the number left parenthesis is larger than the right one, or either of them is less than 0, return.

public List generateParenthesis(int n) {
        List rst = new ArrayList ();
        if (n <= 0)
            return rst;
        getParenthesis("", rst, n, n);
        return rst;
    }
    private void getParenthesis(String p, List rst, int left, int right) {
        if (left > right || left < 0 || right < 0)
            return;
        if (left == 0 && right == 0) {
            rst.add(p);
            return;
        }
        getParenthesis(p + "(", rst, left - 1, right);
        getParenthesis(p + ")", rst, left, right - 1);
    }