# 题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
@前端进阶之旅: 代码已经复制到剪贴板
给出 n = 2, 生成结果为:
[
"(())",
"()()"
]
@前端进阶之旅: 代码已经复制到剪贴板
# 解题思路
LeetCode里有很多种解题思路: 回溯、动态规划等等.
在这里我主要讲解一种最简单最好理解的方法.
思路:
- 输入n, 则就表示会有n个左括号和n个右括号;
- 使用递归的方式, 用两个变量
l和r分别记录使用了左括号的数量和右括号的数量; - 当
l小于n的时候, 则添加上左括号(, 且后面添加的右括号)都不能大于l.
# Coding
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
let res = [];
let cycle = (currentStr, l, r) => {
if (l === n && r === n) { // 当左右括号数量和n相等则返回
res.push(currentStr);
return;
}
if (l < n) { // 若左括号的数量小于n
cycle(currentStr + '(', l + 1, r);
}
if (l > r) { // 若左括号的数量大于右括号数量
cycle(currentStr + ')', l, r + 1);
}
};
cycle('', 0, 0);
return res;
};
@前端进阶之旅: 代码已经复制到剪贴板
执行用时: 60ms, 内存消耗: 35.2MB.
