知一的指纹

22. 括号生成

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

1
2
3
4
5
6
7
8
9
10
11
12
[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路

根据递归做暴力处理,同时进行剪枝操作。

解答

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
26
27
28
29
import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
public static void main(String[] args) {
GenerateParenthesis obj = new GenerateParenthesis();
List<String> stringList = obj.generateParenthesis(3);
System.out.println(stringList);
}

public List<String> generateParenthesis(int n) {
List<String> collect = new ArrayList<>();
gen(collect, "", n, n);
return collect;
}

public void gen(List<String> collect, String cur, int left, int right) {
if (left == 0 && right == 0) {
collect.add(cur);
return;
}
if (left > 0) {
gen(collect, cur + "(", left - 1, right);
}
if (right > 0 && right > left) {
gen(collect, cur + ")", left, right - 1);
}
}
}

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏