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

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

解法：leetcode上的解法很赞。 其实这也是利用的递归的分支。构建了一树状结构并遍历，叶子节点就是valid的结果。

 1 public static ArrayList<String> generateParenthesis(int n) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         ArrayList<String> result = new ArrayList<String>();
 5         generate(result, "",0,0,n);
 6         return result;
 7     }
 8     
 9     private static void generate(ArrayList<String> result, String prefix, int leftCount, int rightCount,int totalPairs){
10         if(leftCount == totalPairs){
11             for(int i = 0; i < totalPairs - rightCount;i++){
12                 prefix += ")";
13             }
14             result.add(prefix);
15             return;
16         }
17         generate(result, prefix + "(", leftCount + 1, rightCount, totalPairs);
18         if(leftCount > rightCount) generate(result, prefix +")", leftCount, rightCount + 1,totalPairs);
19     }

Generate Parentheses