Leetcode Generate Parentheses

题目：http://oj.leetcode.com/problems/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:

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

加括号总数本质上就是一个卡特兰数，因此我的解法跟卡特兰递推式的计算过程一样，因此，要得到n对括号的排列，得先得到1~n-1对括号的排列（当然如果需多次调用该方法以得到多个加括号方式的话，可以保存之前计算得到的值，避免重复计算），具体代码如下：

import java.util.ArrayList;

public class GenerateParentheses {
	ArrayList<ArrayList<String>> list;

	private void genParenthesis(int n, int st, int ed, StringBuilder sb,
			ArrayList<String> innerList) {
		if (st == ed) {
			innerList.add(sb.toString());
		} else {
			if (ed == 2 * n)
				sb.append(")");
			int len = (ed - st - 1) / 2;
			if (len == 0) {
				genParenthesis(n, ed, 2 * n, sb, innerList);
			} else {
				for (int k = 0; k < list.get(len).size(); k++) {
					sb.append(list.get(len).get(k));
					genParenthesis(n, ed, 2 * n, sb, innerList);
					sb.delete(sb.length() - list.get(len).get(k).length(),
							sb.length());
				}
			}
			if (ed == 2 * n) {
				sb.deleteCharAt(sb.length() - 1);
			}
		}
	}

	public ArrayList<String> generateParenthesis(int n) {
		list = new ArrayList<ArrayList<String>>();
		ArrayList<String> innerList = new ArrayList<String>();
		list.add(innerList);
		innerList = new ArrayList<String>();
		innerList.add("()");
		list.add(innerList);
		if (n <= 1)
			return list.get(n);
		StringBuilder sb = new StringBuilder();
		sb.append("(");
		for (int i = 2; i <= n; i++) {
			innerList = new ArrayList<String>();
			for (int j = 1; j < 2 * i; j += 2) {
				genParenthesis(i, 0, j, sb, innerList);
			}
			list.add(innerList);
		}
		System.out.println("Size: " + list.get(n).size() + "\n" + list.get(n));
		return list.get(n);
	}

	public static void main(String[] args) {
		GenerateParentheses gp= new GenerateParentheses();
		gp.generateParenthesis(4);
	}
}