第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0022. 括号生成

题目地址(22. 括号生成)

题目描述

1
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
2
3
示例:
4
5
输入:n = 3
6
输出:[
7
"((()))",
8
"(()())",
9
"(())()",
10
"()(())",
11
"()()()"
12
]
Copied!

前置知识

  • DFS
  • 回溯法

公司

  • 阿里
  • 百度
  • 腾讯
  • 字节

思路

本题是 20. 有效括号 的升级版。
由于我们需要求解所有的可能, 因此回溯就不难想到。回溯的思路和写法相对比较固定,并且回溯的优化手段大多是剪枝。
不难想到, 如果左括号的数目小于右括号,我们可以提前退出,这就是这道题的剪枝。 比如 ())....,后面就不用看了,直接退出即可。回溯的退出条件也不难想到,那就是:
  • 左括号数目等于右括号数目
  • 左括号数目 + 右括号数目 = 2 * n
由于我们需要剪枝, 因此必须从左开始遍历。(WHY?)
因此这道题我们可以使用深度优先搜索(回溯思想),从空字符串开始构造,做加法, 即 dfs(左括号数, 右括号数目, 路径), 我们从 dfs(0, 0, '') 开始。
伪代码:
1
res = []
2
def dfs(l, r, s):
3
if l > n or r > n: return
4
if (l == r == n): res.append(s)
5
# 剪枝,提高算法效率
6
if l < r: return
7
# 加一个左括号
8
dfs(l + 1, r, s + '(')
9
# 加一个右括号
10
dfs(l, r + 1, s + ')')
11
dfs(0, 0, '')
12
return res
Copied!
由于字符串的不可变性, 因此我们无需撤销 s 的选择。但是当你使用 C++ 等语言的时候, 就需要注意撤销 s 的选择了。类似:
1
s.push_back(')');
2
dfs(l, r + 1, s);
3
s.pop_back();
Copied!

关键点

  • 当 l < r 时记得剪枝

代码

  • 语言支持:JS,Python3,CPP
JS Code:
1
/**
2
* @param {number} n
3
* @return {string[]}
4
* @param l 左括号已经用了几个
5
* @param r 右括号已经用了几个
6
* @param str 当前递归得到的拼接字符串结果
7
* @param res 结果集
8
*/
9
const generateParenthesis = function (n) {
10
const res = [];
11
12
function dfs(l, r, str) {
13
if (l == n && r == n) {
14
return res.push(str);
15
}
16
// l 小于 r 时不满足条件 剪枝
17
if (l < r) {
18
return;
19
}
20
// l 小于 n 时可以插入左括号,最多可以插入 n 个
21
if (l < n) {
22
dfs(l + 1, r, str + "(");
23
}
24
// r < l 时 可以插入右括号
25
if (r < l) {
26
dfs(l, r + 1, str + ")");
27
}
28
}
29
dfs(0, 0, "");
30
return res;
31
};
Copied!
Python Code:
1
class Solution:
2
def generateParenthesis(self, n: int) -> List[str]:
3
res = []
4
def dfs(l, r, s):
5
if l > n or r > n: return
6
if (l == r == n): res.append(s)
7
if l < r: return
8
# 加一个左括号
9
dfs(l + 1, r, s + '(')
10
# 加一个右括号
11
dfs(l, r + 1, s + ')')
12
dfs(0, 0, '')
13
return res
Copied!
CPP Code:
1
class Solution {
2
private:
3
vector<string> ans;
4
void generate(int leftCnt, int rightCnt, string &s) {
5
if (!leftCnt && !rightCnt) {
6
ans.push_back(s);
7
return;
8
}
9
if (leftCnt) {
10
s.push_back('(');
11
generate(leftCnt - 1, rightCnt, s);
12
s.pop_back();
13
}
14
if (rightCnt > leftCnt) {
15
s.push_back(')');
16
generate(leftCnt, rightCnt - 1, s);
17
s.pop_back();
18
}
19
}
20
public:
21
vector<string> generateParenthesis(int n) {
22
string s;
23
generate(n, n, s);
24
return ans;
25
}
26
};
Copied!
复杂度分析
  • 时间复杂度:O(2^N)
  • 空间复杂度:O(2^N)
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。