复盘 · LC 22 括号生成

题目

题号：LeetCode 22
名称：括号生成（Generate Parentheses）
难度：Medium
链接：leetcode.cn/problems/generate-parentheses/
今日代码：22-括号生成/index.js

题意

给定 n，生成所有由 n 对括号组成的有效括号字符串。

有效：任意前缀中 ( 数量 ≥ ) 数量，且总长 2n。
边界：n = 1 → ["()"]；n = 0 → [""]（LeetCode 约定）。

涉及算法

标签	一句话
回溯 + 约束	左括号未满可放 `(`；右括号数 < 左括号数才可放 `)`
决策树剪枝	非法分支（先右后左导致前缀无效）在递归入口就不进入

教程对照：20 · 回溯经典（括号生成是「带约束的回溯」代表题）。

评价我的解法

用了「左括号放满 n 个后，一次性补全右括号」的变体，能出正确结果，但和标准「左右同时决策」相比冗余大、常数高（击败 5.87%）。

我的代码（摘自 22-括号生成/index.js，不含测例）：

javascript

var generateParenthesis = function (n) {
  const resArr = [];
  const tmpRes = [];
  let leftNum = 0;
  let rightNum = 0;

  function dfs() {
    if (leftNum === n) {
      const arr = [
        ...tmpRes,
        ...Array.from({ length: leftNum - rightNum }).fill(")"),
      ];
      resArr.push(arr.join(""));
      return;
    }
    if (leftNum <= rightNum) {
      tmpRes.push("(");
      leftNum++;
      dfs();
      leftNum--;
      tmpRes.pop();
    } else {
      tmpRes.push("(");
      leftNum++;
      dfs();
      leftNum--;
      tmpRes.pop();

      tmpRes.push(")");
      rightNum++;
      dfs();
      rightNum--;
      tmpRes.pop();
    }
  }
  dfs();
  return resArr;
};

问题与可改进点：

叶子处批量补 )：leftNum === n 时 spread + Array.from 拼串，每个合法串都多分配临时数组，常数差。
if / else 两分支重复「加左括号」四行：应合并为「能加左就加左；能加右再加右」两个独立 if，而不是互斥 else。
条件 leftNum <= rightNum 只走左：在 left === right 时只能加 (，这对；但 else 里又写一遍加 (，结构绕。
缺少 n === 0：按题意应返回 [""]，当前 dfs 会直接 push 空串，碰巧可能对，但应用标准边界显式处理。
命名：leftNum / rightNum 清晰；tmpRes 作路径 OK。

小结：约束直觉（右不能超过左）有了，实现走捷径「最后补右括号」+ 重复代码，导致性能和可读性都偏弱；应改默写双 if 标准模板。

最佳题解

javascript

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = [];
  const path = [];

  function dfs(left, right) {
    if (path.length === 2 * n) {
      res.push(path.join(""));
      return;
    }
    if (left < n) {
      path.push("(");
      dfs(left + 1, right);
      path.pop();
    }
    if (right < left) {
      path.push(")");
      dfs(left, right + 1);
      path.pop();
    }
  }

  dfs(0, 0);
  return res;
};

时间 O(4^n / √n)（卡特兰数），空间 O(n) 栈。
为何更优：每条边只 push/pop 一次字符，无叶子批量补括号；两个 if 并列，口述「左未满 / 右少于左」即可。

关联题目

题	为何相关
20. 有效的括号	验证合法性，栈或计数器
32. 最长有效括号	括号匹配 Hard
301. 删除无效的括号	BFS/回溯删最少字符
17. 电话号码的字母组合	同为构造字符串的回溯

一句话带走

括号生成回溯：左括号没用完就能放 (，且只有 right < left 时才能放 )，两条规则并列 try，别拖到叶子再补右括号。

复盘 · LC 22 括号生成 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​