题目：

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:

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

 

题解：

 这道题跟unique binary tree ii是类似的。如果是只求个数的话是类似unique binary tree，用到了卡特兰数。

这里也是用到了类似的模型。

 

不过这道题按照DFS那种递归想法解决还是比较容易想到的。

给定的n为括号对，所以就是有n个左括号和n个右括号的组合。

按顺序尝试知道左右括号都尝试完了就可以算作一个解。

注意，左括号的数不能大于右括号，要不然那就意味着先尝试了右括号而没有左括号，类似“)(” 这种解是不合法的。

 

代码如下：

 1     

public ArrayList<String> generateParenthesis(

int n) {  

 2         ArrayList<String> res = 

new ArrayList<String>();

 3         String item = 

new String();

 4         

 5         

if (n<=0)

 6             

return res;  

 7             

 8         dfs(res,item,n,n);  

 9         

return res;  

10     }  

11       

12     

public 

void dfs(ArrayList<String> res, String item, 

int left, 

int right){ 

13         

if(left > right)

//

deal wiith ")("

14 

            

return;

15             

16         

if (left == 0 && right == 0){  

17             res.add(

new String(item));  

18             

return;  

19         }

20         

21         

if (left>0) 

22             dfs(res,item+'(',left-1,right);  

23         

if (right>0) 

24             dfs(res,item+')',left,right-1);  

25     } 

Reference：

http://blog.csdn.net/linhuanmars/article/details/19873463

http://blog.csdn.net/u011095253/article/details/9158429