Generate Parentheses leetcode java
2024-08-20 08:45:30
题目:
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; } public void dfs(ArrayList<String> res, String item, int left, int right){ if(left > right)//deal wiith ")(" return; if (left == 0 && right == 0){ res.add(new String(item)); return; } if (left>0) dfs(res,item+'(',left-1,right); if (right>0) dfs(res,item+')',left,right-1); }
Reference:
http://blog.csdn.net/linhuanmars/article/details/19873463
http://blog.csdn.net/u011095253/article/details/9158429
最新文章
- ASM磁盘组扩容流程
- Java开发程序,使用编辑器编写创建Java项目、类
- putty-不输入密码直接登陆
- django base.html
- [BZOJ2794][Poi2012]Cloakroom
- javascript一种新的对象创建方式-Object.create()
- linux知识点
- picLazyLoad 图片延时加载,包含背景图片
- Oracle12c中新建用户
- <;转>;Java 理论与实践: 正确使用 Volatile 变量
- VC++6.0中各种文件的作用
- C++ 库研究笔记——通过inline避免hpp 的mutiple definition 错误
- expect 参数处理之一
- STM32伺服编码器接口
- js常见排序
- 使用freemarker模板引擎生成word文档的开发步骤
- Android之Error: &#39;L&#39; is not a valid file-based resource name character解决办法
- 转-编写CGI小结
- C语言 &#183; 年龄巧合
- PHP中的=>;,->;,@,&;,::,%
热门文章
- leetcode 岛屿的个数 python
- NCTF2018 Easy_Audit的writeup
- hdu 4460 第37届ACM/ICPC杭州赛区H题 STL+bfs
- sqlserver -- 查看当前数据库的数据表(备忘)
- BZOJ 3564: [SHOI2014]信号增幅仪 最小圆覆盖
- 在Ubuntu的系统中怎样将应用程序加入到開始菜单中
- swap文件查看
- android开发之GestureDetector手势识别(调节音量、亮度、快进和后退)
- mybatis中的updateByExampleSelective方法怎么使用
- 从零开始,运行一个android例子程序