Generate Parentheses leetcode java
题目:
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个右括号的组合。
按顺序尝试知道左右括号都尝试完了就可以算作一个解。
注意,左括号的数不能大于右括号,要不然那就意味着先尝试了右括号而没有左括号,类似“)(” 这种解是不合法的。
代码如下:
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
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。