LeetCode(22) － Generate Parentheses

　　题目要求给你一个数字n，代表有n个括号()。然后输出n个括号可能的组合。如n＝2时，就是"()() (())"。

　　如以前讲过，当需要列出所有可能的组合的时候，我们优先想到的就是backtracking。思路大概是这样子：用两个数字left和right纪录当前“剩余”（还没有没有加上）的括号数，对于其中一层递归，当加一个左括号，left减1，进入下一层。而在当层，如果right > left，就加一个右括号，进入另外一个递归。知道left = right = 0为止，递归结束。

　　代码如下：

 1 public class Solution {
 2     public List<String> generateParenthesis(int n) {
 3         List<String> list = new ArrayList<String>();
 4         if (n > 0) {
 5             generateParenthesisHelper(list,"",n,n);
 6         }
 7         return list;
 8     }
 9     
10     private void generateParenthesisHelper(List<String> list, String s, int left, int right) {
11         //递归结束条件。
12         if (right == 0) {
13             list.add(s);
14             return;
15         }
16         
17         //当left>0，加一个"("，left－1，进入下一层。
18         if (left > 0) {
19             generateParenthesisHelper(list,s + "(",left-1,right);
20         }
21         
22         //当right>left，加一个")"，right－1，进入另一个递归（比上面递归多一个右括号）。
23         if (right > left) {
24             generateParenthesisHelper(list,s + ")",left,right-1);
25         }
26     }
27 }