# 22 括号生成
# 题目链接
# 难度：中等
# 思路分析：
树思想 回溯
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
树思想 回溯 深度优先遍历
var generateParenthesis2 = function(n) {
let left = (right = n); // 左右分支的数量
let res = [];
if (n == 0) {
return res;
}
dfs("", left, right);
function dfs(preStr, left, right) {
// 当没有括号时 即回溯终止
if (left === 0 && right === 0) {
res.push(preStr);
return;
}
// 当成一颗深度为2n的树来做 每个括号在这棵树内都会都用到
// 剪枝: 左括号可以使用的个数严格大于右括号可以使用的个数时 左侧也会生出分支准备生出右侧的括号
if (left > right) {
return;
}
// 一次添加左侧一次添加右侧 回溯 凑成括号
if (left > 0) {
dfs(`${preStr}(`, left - 1, right);
}
if (right > 0) {
dfs(`${preStr})`, left, right - 1);
}
}
return res;
};
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
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
回溯加法方式 深度优先遍历
var generateParenthesis3 = function(n) {
let res = [];
dfs("", 0, 0);
function dfs(preStr, left, right) {
// 括号数量用完了 取消回溯
if (left === n && right === n) {
res.push(preStr);
return;
}
// 当左边的数量小于右边时 左侧也会生出分支准备生出右侧的括号
if (left < right) {
return;
}
// 一次添加左侧一次添加右侧 回溯 凑成括号
if (left < n) {
dfs(`${preStr}(`, left + 1, right);
}
if (right < n) {
dfs(`${preStr})`, left, right + 1);
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧