题目描述如下：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
1
2
3
4
5
6
7
8
| 输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
|
暴力破解
初看这一题，首先想到的是n个左括号和n个右括号的数组进行全排列得到所有的序列，然后从序列中过滤出合法的括号序列和重复序列(因为字符是有重复的，可能导致全排列本身中出现序列重复)，
代码如下：
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
38
39
40
41
42
43
44
45
46
47
| var generateParenthesis = function (n) {
const arr = [];
while (n--) {
arr.push('(');
arr.push(')');
}
function isValid(arr) {
let balance = 0;
for (const c of arr) {
if (c === '(') {
balance++;
} else if (c === ')') {
balance--;
if (balance < 0) return false;
}
}
return balance === 0;
}
const set = new Set();
function dfs(index) {
if (index === arr.length) {
set.add(arr.join(''));
return;
}
for (let i = index; i < arr.length; i++) {
[arr[index], arr[i]] = [arr[i], arr[index]];
dfs(index + 1);
[arr[index], arr[i]] = [arr[i], arr[index]];
}
}
dfs(0);
const ret = [];
for (const item of set) {
if (isValid(item.split(''))) {
ret.push(item);
}
}
return ret;
}
|
以上暴力破解的复杂度为O(2N!)，提交后超时了。
回溯法
方案1的改进，只在序列仍然保持有效时才添加 ‘(‘ or ‘)’，而不是像方案1那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，如果左括号数量小于n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const res = [];
function backtrack(s, l, r) {
if (s.length === 2 * n) {
res.push(s.join(''));
return;
}
if (l < n) {
s.push('(');
backtrack(s, l + 1, r);
s.pop();
}
if (r < l) {
s.push(')');
backtrack(s, l, r + 1);
s.pop();
}
}
backtrack([], 0, 0);
return res;
|
深度优先搜索
我们以 n = 2 为例，画树形结构图。方法是 “做减法”。
画图以后，可以分析出的结论：
- 当前左右括号都有大于0个可以使用的时候，才产生分支；
- 产生左分支的时候，只看当前是否还有左括号可以使用；
- 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
- 在左边和右边剩余的括号数都等于0的时候结算。
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
| var generateParenthesis = function (n) {
const res = [];
function dfs(curStr, leftRemain, rightRemain) {
if (leftRemain === 0 && rightRemain === 0) {
res.push(curStr);
return;
}
if (leftRemain > rightRemain) {
return;
}
if (leftRemain > 0) {
dfs(curStr + '(', leftRemain - 1, rightRemain);
}
if (rightRemain > 0) {
dfs(curStr + ')', leftRemain, rightRemain - 1);
}
}
dfs('', n, n);
return res;
};
|
如果我们不用减法，使用加法，即 leftUsed 表示“左括号用掉几个”，rightUsed 表示“右括号用掉几个”，可以画出另一棵递归树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function dfs2(curStr, leftUsed, rightUsed) {
if (leftUsed === n && rightUsed === n) {
res.push(curStr);
return;
}
if (leftUsed < rightUsed) {
return;
}
if (leftUsed < n) {
dfs2(curStr + '(', leftUsed + 1, rightUsed);
}
if (rightUsed < n) {
dfs2(curStr + ')', leftUsed, rightUsed + 1);
}
}
|
广度优先搜索
通过编写广度优先遍历的代码，读者可以体会一下，为什么搜索几乎都是用深度优先遍历（回溯算法）。
广度优先遍历，得程序员自己编写结点类，显示使用队列这个数据结构。深度优先遍历的时候，就可以直接使用系统栈，在递归方法执行完成的时候，系统栈顶就把我们所需要的状态信息直接弹出，而无须编写结点类和显示使用栈。
下面的代码，可以把 Queue 换成 Stack，提交以后，也可以得到 Accept。
读者可以通过比较：
1、广度优先遍历；
2、自己使用栈编写深度优先遍历；
3、使用系统栈的深度优先遍历（回溯算法）。
来理解 “回溯算法” 作为一种 “搜索算法” 的合理性。
还是上面的题解配图（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
| class Node {
constructor(str, leftRemain, rightRemain) {
this.str = str;
this.leftRemain = leftRemain;
this.rightRemain = rightRemain;
}
}
const res = [];
const q = [new Node('', n, n)];
while (q.length) {
const { str, leftRemain, rightRemain } = q.shift();
if (leftRemain === 0 && rightRemain === 0) {
res.push(str);
}
if (leftRemain > rightRemain) {
continue;
}
if (leftRemain > 0) {
q.push(new Node(str + '(', leftRemain - 1, rightRemain));
}
if (rightRemain > 0) {
q.push(new Node(str + ')', leftRemain, rightRemain - 1));
}
}
|
