leetCode-括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
1
2
| 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
|
示例 2：
解法一（DFS）
过程：
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
returnList(new String(),n,n);
return res;
}
public void returnList(String s,int left,int right){
if (left==0 && right==0){
res.add(s);
return;
}
if (left>right){
return;
}
if (left>0){
returnList(s+'(',left-1,right);
}
if (right>0){
returnList(s+')',left,right-1);
}
}
}
|
解法二（慢慢 分析）
回溯的灵魂就是画出数的结构图，首先先将所有的情况都列出：
观察上图就是一个满二叉树，我们只需要DFS去遍历所有的节点即可，先把最基本的实现，热后再去改进，
基本的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
returnList(new String(),n);
return res;
}
public void returnList(String s,int n) {
if (s.length() == 2*n) {
res.add(s);
return;
}
returnList(s + '(',n);
returnList(s + ')', n);
}
|
结果为：
1
| ["((((","((()","(()(","(())","()((","()()","())(","()))",")(((",")(()",")()(",")())","))((","))()",")))(","))))"]
|
观察不需要的括号特点，((((和))))实际上已经超过n了，我们生成同一方向的括号只需要n个即可，在生成的时候我们要限制住左括号与右括号生成的数量
这时我增加了left与right参数，分别代表左括号与右括号的数量，每生成一个我就增加一个。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
returnList(new String(),0,0,n);
return res;
}
public void returnList(String s,int left,int right,int n) {
if (left>n || right>n) return;
if (right>left) return;
if (s.length() == 2*n) {
res.add(s);
return;
}
returnList(s + '(', left+1,right,n);
returnList(s + ')', left,right+1,n);
}
}
|