http://www.lintcode.com/en/problem/generate-parentheses/

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

Example Given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()"

解题：backtracking这类型题都可以画图找思路，如果遇到类似要找各种combination的题基本可以这样求解。下图很清晰的描述了n=3括号配对的全过程。

      n = 3
                []
               / 
               (
       /             \  
     ((               ()
    /   \             |  
 (((     (()          ()(
        /   \         |    \
      (()(   (())   ()((  ()()
              |             \
            (())(           ()()(

public class Solution {
    public List<String> generateParenthesis(int n) {
        // write your code here
        List<String> result = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        if (n > 0) generate(n, path, result, 0, 0);
        return result;
    }
    // l 表示 ( 出现的次数, r 表示 ) 出现的次数
    private static void generate(int n, StringBuilder path,
                                 List<String> result, int l, int r) {
        if (l == n) {
            //当（用完了，补足需要的)
            StringBuilder sb = new StringBuilder(path);
            for (int i = 0; i < n - r; ++i) sb.append(')');
            result.add(sb.toString());
            return;
        }

        path.append('(');
        generate(n, path, result, l + 1, r);
        path.deleteCharAt(path.length() - 1);

        if (l > r) {
            path.append(')');
            generate(n, path, result, l, r + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}