[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对括号，生成所有合法的组合情况。

思路：合法的情况是，任意一时刻，左（“(”）括号数要大于等于右（")"）括号数。关键在于题中只给了括号的对数，没有形象的左右括号字符，如何在脑海中转过弯去解题。故，在某次的调用中，

1）left大于right（left和right分别表示剩余左右括号的个数），即，临时变量中右括号的数大于左括号的数，则说明出现了“)(”，这是非法情况，返回即可；

2）left和right都等于0说明，临时变量中左右括号数相等，所以将临时变量中的值存入res中；

3）其余的情况是，先放左括号，然后放右括号，然后递归。注意参数的更新。

参考了Grandyang的博客。代码如下;

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) 
 4     {
 5         vector<string> res;
 6         generateDFS(n,n,"",res);
 7         return res;    
 8     }
 9 
10     /*left、right分别是左右括号剩下的括号数*/
11     void generateDFS(int left,int right,string temp,vector<string> &res)
12     {
13         if(left>right) return;
14         if(left==0&&right==0)  
15             res.push_back(temp);
16         else
17         {
18             if(left>0)
19                 generateDFS(left-1,right,temp+'(',res);
20             if(right>0)
21                 generateDFS(left,right-1,temp+')',res);
22         }
23     }
24 };

方法二：这种解法中left和right分别表示临时变量中的左右括号数，这是和方法一不一样的地方。先加入左括号，然后在右括号比左括号少，即合法的情况下，再加入右括号。参考糖豆009。代码如下：

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) 
 4     {
 5         vector<string> res;
 6         string temp;
 7         generateParenthesisDFS(n,0,0,temp,res);
 8         return res;
 9     }
10 
11     void generateDFS(int n,int left,int right,string &temp,vector<string> & res)
12     {
13         if(left<n)
14         {
15             temp.push_back('(');
16             generateDFS(n,left+1,right,temp,res);
17             temp.pop_back();
18         }
19 
20         if(right<left)  //避免出现右括号比左括号多的情况。
21         {
22             temp.push_back(')');
23             generateDFS(n,left,right+1,temp,res);
24             temp.pop_back();
25         }
26         if(temp.size()==n*2)
27             res.push_back(temp);
28     }
29     
30 };