https://leetcode-cn.com/problems/generate-parentheses/submissions/
使用递归+双层循环的方式来解决。主要思路是将当前状态中所有可以成对的可能性都考虑到，先考虑左括号，再考虑右括号。然后让每种可能性都递归下去。
代码还有 bug（因为结果会产生许多长度不满足的数组），不过已经可以 Accept 了，而且只击败了 24% 的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<String> ret;
public void gp(int n, int l, int r, String nowStr){
if(l==n && r==n){
if(nowStr.length()==n*2) ret.add(nowStr);
}
String ts1=nowStr;
while(l<n){
l++;
String ts2=ts1+"(";
gp(n,l,r,ts2);
while(r<l){
r++;
ts2=ts2+")";
gp(n,l,r,ts2);
}
}
}
public List<String> generateParenthesis(int n) {
ret=new ArrayList<>();
gp(n,0,0,"");
return ret;
}
}
|
经过检查，是因为 Java 的字符串赋值是传递地址的，必须使用传递值才可以。所以有了如下的方案，但是因为会出现重复结果，所以使用了 HashSet 转 ArrayList。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public Set<String> res;
public void gp(int n, int l, int r, String nowStr){
if(l==n && r==n) res.add(nowStr);
while(l++<n){
nowStr+="(";
gp(n,l,r,nowStr);
String ts=new String(nowStr);
int tr=r;
while(tr++<l){
ts=ts+")";
gp(n,l,tr,ts);
}
}
}
public List<String> generateParenthesis(int n) {
res=new HashSet<>();
gp(n,0,0,"");
return new ArrayList<String>(res);
}
}
|
但发现速度更慢了，只击败了 4%的人。原因应该是数组的重复复制以及 hashset 去重。
看了一下 Solutions 中的答案，发现方法二 Backtracking（回溯算法）和我之前的很像，不过我在一次递归中考虑的太多，导致重复。
所以，在回溯里只要考虑下一步做什么就可以了，不要考虑这么多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<String> res;
public void gp(int n, int l, int r, String nowStr){
if(nowStr.length()==n*2){
res.add(nowStr);
return;
}
if(l<n){
gp(n,l+1,r,nowStr+"(");
}
if(r<l){
gp(n,l,r+1,nowStr+")");
}
}
public List<String> generateParenthesis(int n) {
res=new ArrayList<>();
gp(n,0,0,"");
return res;
}
}
|
最后， solution 给出了一个最简单的方法。可以构成成堆的括号的标准就是有一个东西把另外的东西括起来，所以以括号为单位进行递归是最方便的选择。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c)
for (String left: generateParenthesis(c))
for (String right: generateParenthesis(n-1-c))
ans.add("(" + left + ")" + right);
}
return ans;
}
}
|
时间过去了快一年，这里是我现在的解法，同样是回溯法，但简洁了许多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if(n<=0) return result;
generate(result, "", n, 0);
return result;
}
void generate(vector<string>& result, string now, int nleft, int unpaired) {
if(nleft==0 && unpaired==0) {
result.push_back(now);
return;
}
if(nleft!=0) generate(result, now+'(', nleft-1, unpaired+1);
if(unpaired!=0) generate(result, now+')', nleft, unpaired-1);
}
};
|