LeetCode 「中等」22.括号生成
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]
解答
关键思路
- 有效性条件
- 有效的括号组合必须满足：每个右括号
)都有一个对应的左括号(，并且右括号不能出现在左括号之前 - 在生成过程中，我们需要确保：
- 左括号的数量不能超过
n - 右括号的数量不能超过左括号的数量
- 左括号的数量不能超过
- 回溯法
- 使用递归回溯法来生成所有可能的括号组合
- 在递归过程中，逐步添加左括号
(和右括号)，并确保满足有效性条件
- 递归终止条件
- 当左括号和右括号的数量都达到
n时，生成了一个有效的括号组合，将其加入结果列表
具体步骤
- 定义递归函数
- 递归函数需要记录当前生成的括号字符串、左括号的数量和右括号的数量
- 递归逻辑
- 如果左括号的数量小于
n，可以添加一个左括号(，并递归 - 如果右括号的数量小于左括号的数量，可以添加一个右括号
)，并递归
- 剪枝
- 如果左括号或右括号的数量超过了限制，直接返回
- 终止条件：
- 如果左括号和右括号的数量都等于
n，将当前字符串加入结果列表
Code
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
const result = [];
const backtrack = (current, left, right) => {
// 如果左括号和右括号的数量都达到 n，生成了一个有效组合
if (left === n && right === n) {
result.push(current);
return;
}
// 如果左括号的数量小于 n，可以添加一个左括号
if (left < n) {
backtrack(current + '(', left + 1, right);
}
// 如果右括号的数量小于左括号的数量，可以添加一个右括号
if (right < left) {
backtrack(current + ')', left, right + 1);
}
};
// 从空字符串开始，左括号和右括号的数量都为 0
backtrack('', 0, 0);
return result;
}