【LeetCode热题100道笔记】括号生成
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
思考
核心思路是通过“计数约束”和“栈状态”确保括号生成合法：
- 合法性规则：
- 空栈/左括号未达上限（
countLeft < n）时，只能先加左括号（左括号是合法括号的起点）； - 仅当左括号数量 > 右括号数量（
countLeft > countRight）时，才能加右括号（避免出现")("等非法结构）；
- 空栈/左括号未达上限（
- 终止条件：栈长度达到
2n（左+右括号共n对）时，生成一个合法括号组合； - 回溯逻辑：每次添加括号后递归，递归结束后弹出括号、更新计数，恢复状态以尝试其他组合。
算法过程
- 初始化：结果列表
result，计数变量countLeft（左括号数）、countRight（右括号数），栈stack存储当前括号序列； - 递归入口：调用
dfs()，初始栈为空，先添加左括号（唯一合法选择）； - DFS核心逻辑：
- 终止：若栈长度 =
2n，将栈转为字符串加入result，返回； - 加左括号：若
countLeft < n，压栈、countLeft++，递归后回溯（弹栈、countLeft--）； - 加右括号：若
countLeft > countRight，压栈、countRight++，递归后回溯（弹栈、countRight--）；
- 终止：若栈长度 =
- 返回结果：递归结束后，
result包含所有合法组合，返回即可。
时空复杂度
-
时间复杂度：O(4ⁿ/√n)
合法括号组合总数为“卡特兰数”C(n) = (1/(n+1)) * C(2n, n)，渐近复杂度为4ⁿ/√n；每个组合生成需 O(n) 时间（栈转字符串），总时间复杂度为 O(4ⁿ/√n)。 -
空间复杂度：O(n)
递归栈深度最大为2n（对应完整括号序列长度），栈stack最大长度也为2n，但可简化为 O(n)（因2n是n的线性倍数）；额外空间不含结果存储。
代码一
/*** @param {number} n* @return {string[]}*/
var generateParenthesis = function(n) {const result = [];let countLeft = 0;let countRight = 0;const stack = [];const dfs = function() {if (stack.length === n * 2) {result.push(stack.join(''));return;}if (stack.length) {if (countLeft < n) {stack.push('(');countLeft++;dfs();stack.pop();countLeft--;}if (countLeft > countRight) {stack.push(')');countRight++;dfs();stack.pop();countRight--;}} else {stack.push('(');countLeft++;dfs();} };dfs();return result;
};
优化
字符串拼接替代数组操作和参数传递替代全局计数，更简洁。
代码二
/*** @param {number} n* @return {string[]}*/
var generateParenthesis = function(n) {const result = [];// 递归函数：当前字符串、左括号数、右括号数const dfs = (current, left, right) => {// 终止条件：生成n对括号if (current.length === 2 * n) {result.push(current);return;}// 加左括号：左括号数量未达上限if (left < n) {dfs(current + '(', left + 1, right);}// 加右括号：右括号数量小于左括号（保证合法）if (right < left) {dfs(current + ')', left, right + 1);}};// 初始调用：空字符串，0左0右dfs('', 0, 0);return result;
};