# 括号生成
# 问题描述:
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 思路
回溯 + 剪枝
# 解法
/*
* @lc app=leetcode.cn id=22 lang=javascript
*
* [22] 括号生成
*/
// @lc code=start
/**
* @param {number} n
* @return {string[]}
*/
// solution: 回溯 + 剪枝
var generateParenthesis = function(n) {
var res = [];
var initialPath = '';
dfs(res, n, n, initialPath);
return res;
function dfs(res, left, right, path) {
if (left === 0 && right === 0) {
res.push(path);
return;
}
if (left > 0) {
dfs(res, left - 1, right, path + '(');
}
if (left < right) {
dfs(res, left, right - 1, path + ')');
}
}
};
// @lc code=end
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
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