【leetcode】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=2的情况如下图所示：

代码如下：

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4         vector<string> answer;
 5         string s = "";
 6         recursive(answer,n,n,s);
 7         
 8         return answer;
 9     }
10     void recursive(vector<string>& answer,int leftp,int rightp,string s){
11         if(leftp == 0 && rightp == 0)
12             answer.push_back(s);
13         if(leftp > 0)
14         {
15             recursive(answer,leftp-1,rightp,s+'(');
16         }
17         if(rightp >0 && leftp < rightp)
18         {
19             recursive(answer,leftp,rightp-1,s+')');
20         }
21     }
22 };

上述代码中有一点要注意的就是在递归的过程中三个if不是互相独立的关系，就是说不是每次只进一个if，有可能从第一个if递归调用返回以后还要进入下一个if，所以在递归调用过程中不能改变s,leftp或者rightp的值，而只能在传递参数的时候体现出变化。如果把上述第二个if写成如下形式，就会发生错误：

1  if(leftp > 0)
2 {
3       s += '('
4        recursive(answer,leftp-1,rightp,s);
5 }

因为这样从第二个if递归返回后再进入第三个if的时候s已经多加了一个'('，不是最初进入函数时候的s了。

JAVA版本代码：

 1 public class Solution {
 2     public List<String> generateParenthesis(int n) {
 3         StringBuffer current = new StringBuffer();
 4         generateHelper(current, 0, 0,n);
 5         return answer;
 6     }
 7     List<String> answer = new ArrayList<String>();
 8     private void generateHelper(StringBuffer current,int leftp,int rightp,int n){
 9         if(leftp == n && rightp == n)
10         {
11             String temp = current.toString();
12             answer.add(temp);
13             return;
14         }
15         
16         if(leftp < n){
17             current.append('(');
18             generateHelper(current, leftp+1, rightp,n);
19             current.deleteCharAt(current.length()-1);
20         }
21         
22         if(rightp < n  && rightp < leftp){
23             current.append(')');
24             generateHelper(current, leftp, rightp+1,n);
25             current.deleteCharAt(current.length()-1);
26         }
27     }
28 }