题目描述
括号。设计一种算法,打印n对括号的所有合法的(例如,开闭一一对应)组合。
说明:解集不能包含重复的子集。
例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解法
方法一:DFS + 剪枝
题目中 $n$ 的范围为 $[1, 8]$,因此我们直接通过“暴力搜索 + 剪枝”的方式快速解决本题。
我们设计函数 dfs(l, r, t)
,其中 $l$ 和 $r$ 分别表示左括号和右括号的数量,而 $t$ 表示当前的括号序列。那么我们可以得到如下的递归结构:
- 如果 $l \gt n$ 或者 $r \gt n$ 或者 $l \lt r$,那么当前括号组合 $t$ 不合法,直接返回;
- 如果 $l = n$ 且 $r = n$,那么当前括号组合 $t$ 合法,将其加入答案数组
ans
中,直接返回;
- 我们可以选择添加一个左括号,递归执行
dfs(l + 1, r, t + "(")
;
- 我们也可以选择添加一个右括号,递归执行
dfs(l, r + 1, t + ")")
。
时间复杂度 $O(2^{n\times 2} \times n)$,空间复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(l, r, t):
if l > n or r > n or l < r:
return
if l == n and r == n:
ans.append(t)
return
dfs(l + 1, r, t + '(')
dfs(l, r + 1, t + ')')
ans = []
dfs(0, 0, '')
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
private List<String> ans = new ArrayList<>();
private int n;
public List<String> generateParenthesis(int n) {
this.n = n;
dfs(0, 0, "");
return ans;
}
private void dfs(int l, int r, String t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.add(t);
return;
}
dfs(l + 1, r, t + "(");
dfs(l, r + 1, t + ")");
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
function<void(int, int, string)> dfs;
dfs = [&](int l, int r, string t) {
if (l > n || r > n || l < r) return;
if (l == n && r == n) {
ans.push_back(t);
return;
}
dfs(l + 1, r, t + "(");
dfs(l, r + 1, t + ")");
};
dfs(0, 0, "");
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func generateParenthesis(n int) []string {
ans := []string{}
var dfs func(int, int, string)
dfs = func(l, r int, t string) {
if l > n || r > n || l < r {
return
}
if l == n && r == n {
ans = append(ans, t)
return
}
dfs(l+1, r, t+"(")
dfs(l, r+1, t+")")
}
dfs(0, 0, "")
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function generateParenthesis(n: number): string[] {
function dfs(l, r, t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.push(t);
return;
}
dfs(l + 1, r, t + '(');
dfs(l, r + 1, t + ')');
}
let ans = [];
dfs(0, 0, '');
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | impl Solution {
fn dfs(left: i32, right: i32, s: &mut String, res: &mut Vec<String>) {
if left == 0 && right == 0 {
res.push(s.clone());
return;
}
if left > 0 {
s.push('(');
Self::dfs(left - 1, right, s, res);
s.pop();
}
if right > left {
s.push(')');
Self::dfs(left, right - 1, s, res);
s.pop();
}
}
pub fn generate_parenthesis(n: i32) -> Vec<String> {
let mut res = Vec::new();
Self::dfs(n, n, &mut String::new(), &mut res);
res
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | /**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
function dfs(l, r, t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.push(t);
return;
}
dfs(l + 1, r, t + '(');
dfs(l, r + 1, t + ')');
}
let ans = [];
dfs(0, 0, '');
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
private var ans: [String] = []
private var n: Int = 0
func generateParenthesis(_ n: Int) -> [String] {
self.n = n
dfs(l: 0, r: 0, t: "")
return ans
}
private func dfs(l: Int, r: Int, t: String) {
if l > n || r > n || l < r {
return
}
if l == n && r == n {
ans.append(t)
return
}
dfs(l: l + 1, r: r, t: t + "(")
dfs(l: l, r: r + 1, t: t + ")")
}
}
|