括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

约束条件

• 1 <= n <= 8

我的解题过程

第一次尝试：回溯算法

刚开始看到这道题，想到的是要生成所有可能的有效括号组合，这是一个典型的回溯问题。

核心思路是：

• 每次可以选择添加左括号 ( 或右括号 )
• 但要保证生成的括号是有效的

那么什么时候可以添加括号呢？

1. 添加左括号的条件：已使用的左括号数量 < n
2. 添加右括号的条件：已使用的右括号数量 < 已使用的左括号数量

第二个条件是关键：右括号数量不能超过左括号，否则就会出现类似 ")()" 这样的无效括号。

最初的代码逻辑有点问题：

function generateParenthesis(n: number): string[] {
  const res: string[] = [];

  function backtrack(path: string, open: number, close: number) {
    if (open === n) {
      res.push(path);
      return;
    }

    if (open < n) {
      backtrack(path + "(", open + 1, close);
    }

    if (close < open) {
      backtrack(path + ")", open, close + 1);
    }
  }

  backtrack("", 0, 0);
  return res;
}

这个版本的问题在于：终止条件不对。当 open === n 时就返回了，但此时右括号可能还没加完，比如 n=2 时会生成 "((" 这样不完整的字符串。

优化思路：正确的终止条件

修正后的思路：

• 终止条件应该是：当路径长度达到 2*n 时（n 对括号总共 2n 个字符）
• 或者更准确的：当左右括号都用完了（open === n && close === n）

function generateParenthesis(n: number): string[] {
  const res: string[] = [];

  function backtrack(path: string, open: number, close: number) {
    // 终止条件：左右括号都用完了
    if (path.length === 2 * n) {
      res.push(path);
      return;
    }

    // 可以添加左括号
    if (open < n) {
      backtrack(path + "(", open + 1, close);
    }

    // 可以添加右括号（右括号数量 < 左括号数量）
    if (close < open) {
      backtrack(path + ")", open, close + 1);
    }
  }

  backtrack("", 0, 0);
  return res;
}

这个版本的关键点：

1. 终止条件：path.length === 2 * n，确保生成完整的括号组合
2. 剪枝优化：
   • open < n：左括号还没用完才能继续添加
   • close < open：右括号数量必须少于左括号，保证有效性
3. 回溯过程：每次选择添加左括号或右括号，递归构建所有可能的组合

执行过程示例（n=2）

以 n=2 为例，看看递归树是怎样的：

                    ""
                   /  \
                 "("   (不能直接加右括号)
                /  \
              "(("  "()"
              /      /  \
            "(()"  "()(" "()" (终止)
            /        /
         "(()"     "()("
        (终止)      /
                "()()"
               (终止)

最终生成：["(())", "()()"]