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:

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

Note:
Solution: Greedy and Recursive
卡特兰数
这道题其实是关于卡特兰数的，如果只是要输出结果有多少组，那么直接用卡特兰数的公式就可以。特别是其中

这个递推式的定义，很多这类问题都可以归结成这个表达式。这个题对于C的定义就是第一对括号中包含有几组括号。因为第一组括号中包含的括号对数量都不同，所以不会重复，接下来就是一个递归定义，里面又可以继续用更小的C去求组合可能性。

用递归的方法，因为可以归结为子问题去操作。在每次递归函数中记录左括号和右括号的剩余数量，然后有两种选择，一个是放一个左括号，另一种是放一个右括号。当然有一些否定条件，比如剩余的右括号不能比左括号少，或者左括号右括号数量都要大于0。正常结束条件是左右括号数量都为0。算法的复杂度是O(结果的数量)，因为卡特兰数并不是一个多项式量级的数字，所以算法也不是多项式复杂度的。

Take advantage of the feature of parentheses, left side and right side must match each other,  in other words, if there a left side parenthese,  whatever position it is, there must be a right side parenthese to match it.

public class Solution {
    public List generateParenthesis(int n) {
        List result = new ArrayList();
        if(n < 1)
            return result;
            
        int left = n;
        int right = n;
        String current = new String();
        generate(left, right, current, result);
        return result;
    }
    
    public List generate(int left, int right, String current, List result) {
        if(left == 0 && right == 0) {
            result.add(current);
            return result;
        }
        
        if(left > 0) {
            generate(left - 1, right, current + '(', result);
        }
        
        if(right > left) {
            generate(left, right - 1, current + ')', result);
        }
        return result;
    }
}

Or: StringBuilder比String更加省空间，但是要注意返回的时候将最后一位删除

public class Solution {
    public List generateParenthesis(int n) {
        ArrayList res = new ArrayList();
        if (n <= 0) {
            return res;
        }
        
        int left = n;
        int right = n;
        StringBuilder sb = new StringBuilder();
        generate(left, right, sb, res);
        
        return res;
    }
    
    public void generate(int left, int right, StringBuilder sb, ArrayList res) {
        if (left == 0 && right == 0) {
            res.add(sb.toString());
            return;
        }
        
        if (left > 0) {
            generate(left - 1, right, sb.append("("), res);
            sb.deleteCharAt(sb.length() - 1);  //还原现场
        }
        
        if (right > left) {
            generate(left, right - 1, sb.append(")"), res);
            sb.deleteCharAt(sb.length() - 1);  //还原现场
        }
    }
}