（LeetCodeHot100）22. 括号生成——generate-parentheses

zhangzhang2025-12-022025-12-07

22. 括号生成——generate-parentheses

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

答案：回溯算法 + 约束剪枝

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("", n, n);
        return res;
    }

private void dfs(String str, int left, int right) {
    if (left == 0 && right == 0) {
        ans.add(str);
    }
    // 左括号可以无脑加
    if (left > 0) {
        dfs(str + "(", left - 1, right);
    }
    // 只有在缺右括号的时候才能加右括号
    if (left < right) {
        dfs(str + ")", left, right - 1);
    }
}

这段代码是生成 n 对有效括号的 最优简洁写法，核心是「回溯算法 + 约束剪枝」—— 既保证不遗漏所有合法组合，又通过两个关键约束过滤掉所有无效组合，最终精准生成所有 Catalan(n) 个有效括号（Catalan(n) 是第 n 个卡特兰数，对应 n 对括号的有效组合数）。

逐行拆解 + 核心逻辑解释

我们从「递归函数定义 → 终止条件 → 约束剪枝 → 递归过程」一步步讲清楚：

1. 整体框架：递归函数 `dfs` 是干什么的？

1	private void dfs(String str, int left, int right)

参数含义：
- str：当前正在构建的括号字符串（比如 "(("、"()" 等中间状态）；
- left：还能使用的左括号数量（初始为 n，用一次减 1）；
- right：还能使用的右括号数量（初始为 n，用一次减 1）；
核心目的：从当前状态出发，尝试添加左 / 右括号，递归构建所有合法的括号字符串，直到耗尽所有括号（left=0 && right=0）。

2. 终止条件：什么时候才算一个有效结果？

1
2
3

if (left == 0 && right == 0) {
    ans.add(str);
}

当「剩余左括号」和「剩余右括号」都用完时，说明当前构建的 str 是一个长度为 2n 的完整有效括号（因为左括号总数 = 右括号总数 = n），直接加入结果集 ans。

3. 约束剪枝：为什么这两个 `if` 能保证 “不无效、不遗漏”？

这是代码的灵魂 —— 两个 if 分别控制 “加左括号” 和 “加右括号” 的条件，既避免生成无效组合，又能覆盖所有合法组合。

（1）加左括号的条件：`if (left > 0)` → “有剩就加”

1
2
3

if (left > 0) {
    dfs(str + "(", left - 1, right);
}

逻辑：只要还有未使用的左括号（left > 0），就可以直接在当前字符串 str 后加一个 (，同时剩余左括号数减 1。
为什么 “无脑加” 不会出错？

左括号是有效括号的 “基础”—— 任何合法括号的前缀中，左括号数量都不会超过n（因为我们最多加n个左括号），且左括号多了不会导致 “前缀右括号多于左括号”（比如”((“是合法前缀，”())”才是无效的）。所以加左括号的唯一约束就是 “还有剩余”，这一步不会生成无效前缀。

（2）加右括号的条件：`if (left < right)` → “缺右才加”

1
2
3

if (left < right) {
    dfs(str + ")", left, right - 1);
}

逻辑：只有当「剩余左括号数 < 剩余右括号数」时，才能加右括号，加完后剩余右括号数减 1。
为什么要这个束？（最关键的一步！）

核心是避免「前缀中右括号多于左括号」—— 这是无效括号的典型特征（比如”)”、”())(“等）。
- 举例：如果当前剩余 left=1、right=2（说明已经用了 n-1 个左括号、n-2 个右括号），此时前缀中左括号比右括号多 1 个，加一个右括号会让前缀左 / 右括号数相等，是合法的；
- 反例：如果 left=2、right=2（剩余数相等），此时加右括号会导致前缀右括号数 = 左括号数 + 1（比如初始时加 ")"，直接无效），所以这个约束会直接过滤掉这种情况。

4. 递归过程：如何遍历所有合法路径？

我们用 n=2 举例，直观看看递归是怎么生成所有有效组合的（n=2 时有效组合有 2 个："()()"、"(())"）：

初始调用：dfs("", 2, 2)（空字符串，2 个左括号、2 个右括号可用

1.满足left>0→ 加(→ 调用dfs("(", 1, 2)；

此时left=1 < right=2→ 加)→ 调用dfs("()", 1, 1)；
- 满足left>0→ 加(→ 调用dfs("()(", 0, 1)；
  - left=0 不能加左括号，满足 left<right → 加 ) → 调用 dfs("()()", 0, 0) → 终止，添加 "()()" 到结果；
- 满足 left<right（1=1 不满足）→ 不加右括号；
满足left>0→ 加(→ 调用dfs("((", 0, 2)；left=0不能加左括号，满足left<right→ 加)→ 调用dfs("(()", 0, 1)；
- left=0 不能加左括号，满足 left<right → 加 ) → 调用 dfs("(())", 0, 0) → 终止，添加 "(())" 到结果；