【Leetcode算法题】22. 括号生成

By Long Luo

22. 括号生成

  1. 括号生成

数字nn代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足:左括号必须以正确的顺序闭合。

示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:
输入:n = 1
输出:["()"]

提示:
1 <= n <= 8

方法一:暴力法

思路与算法:

直接生成所有22n2^{2n}个’(‘和’)'字符构成的序列,然后我们检查每一个是否有效即可。

为了生成所有序列,我们可以使用递归。长度为nn的序列就是在长度为n1n-1的序列前加一个’(‘或’)’。

为了检查序列是否有效,我们遍历这个序列,并使用一个变量balancebalance表示左括号的数量减去右括号的数量。如果在遍历过程中balancebalance的值小于零,或者结束时balancebalance的值不为零,那么该序列就是无效的,否则它是有效的。

代码如下:

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
30
31
32
33
34
35
36
37
public List<String> generateParenthesis(int n) {
if (n < 1) {
return new ArrayList<>();
}

List<String> ans = new ArrayList<>();
generateAll(new char[2 * n], 0, ans);
return ans;
}

public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}

public boolean valid(char[] current) {
int balance = 0;
for (char c : current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}

复杂度分析:

  • 时间复杂度:O(22nn)O(2^{2n}n),对于22n2^{2n}个序列中的每一个,我们用于建立和验证该序列的复杂度为O(n)O(n)

  • 空间复杂度:O(n)O(n),除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)O(1)的空间,最多递归2n2n层,因此空间复杂度为O(n)O(n)

方法二:回溯法

思路与算法:

其实这道题是回溯法的经典练习题,吃透这道题,可以学会解决任何类似回溯题。

方法一没有做剪枝处理,所以造成计算量太大。我们可以只在序列仍然保持有效时才添加’(’ or ‘)’,而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点,

如果左括号数量不大于nn,我们可以放一个左括号。如果右括号数量小于左括号的数量,我们可以放一个右括号。

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
public List<String> generateParenthesis(int n) {
if (n < 1) {
return new ArrayList<>();
}

List<String> ans = new ArrayList<>();
backtrace(ans, new StringBuilder(), 0, 0, n);
return ans;
}

public void backtrace(List<String> ans, StringBuilder sb, int left, int right, int num) {
if (left == right && left == num) {
ans.add(sb.toString());
return;
}

if (left < right || left > num || right > num) {
return;
}

sb.append('(');
backtrace(ans, sb, left + 1, right, num);
sb.deleteCharAt(sb.length() - 1);

sb.append(')');
backtrace(ans, sb, left, right + 1, num);
sb.deleteCharAt(sb.length() - 1);
}

复杂度分析:

  • 时间复杂度:O(4nn)O(\dfrac{4^n}{\sqrt{n}}),在回溯过程中,每个答案需要O(n)O(n)的时间复制到答案数组中。

  • 空间复杂度:O(n)O(n),除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)O(1)的空间,最多递归 2n2n 层,因此空间复杂度为O(n)O(n)

小结

这道题其实可以使用动态规划、DFS、BFS去做,这里就不做引申了,有余力和时间可以做一做。