题目描述
给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。
例子：n = 3，输出：
1
2
3
4
5
| ((()))
(()())
(())()
()(())
()()()
|
思路
递归。
一看这道题就是有通用的解决办法，又是让你输出所有结果，肯定用到递归。
例如n=3，最容易想到（（（））），之后呢？
对于最后一个左括号，如果可以将其改为右括号，就是另一种情况。
所以思路就有了：
1、优先递归输出左括号再输出右括号
2、递归返回时，判断输出最后一个左括号的调用能否输出右括号，能就输出右括号再向下递归
牵扯到判断，所以需要记录当前递归处的左右括号的个数
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| private String s;
private ArrayList<String> res;
public ArrayList<String> generateParenthesis(int n) {
// Write your code here
res = new ArrayList<String>();
produce(n, n, res, "");
return res;
}
private void produce(int left, int right, ArrayList<String>res, String tmp){
if(left == 0 && right == 0)
{
res.add(tmp);
return;
}
if(left > 0){
produce(left-1, right, res, tmp+"(");
}
if(right > 0 && left < right){
produce(left, right-1, res, tmp+")");
}
}
|
考差点