22. 括号生成#

今天要讲的LeetCode 22题「括号生成」看似简单，却暗藏玄机。据统计90%的面试者都在此栽跟头，让我们用最通俗的方式彻底搞懂它！

📝 从生活场景说起#

想象你在编辑器里写代码，VS Code会实时检查括号是否匹配：

每输入一个左括号”(“，就期待后面会有个右括号”)“与之配对
右括号数量不能超过左括号
最终左右括号数量必须相等

这不就是我们今天要解决的问题吗？

问题描述#

题目目标#

给定 n 对括号，请你生成并返回所有可能的有效括号组合。答案可以按任意顺序返回。

示例 1#

输入： n = 3 输出： ["((()))","(()())","(())()","()(())","()()()"] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 题目解析#

题目要求：给定一个正整数n，生成所有可能且有效的括号组合。要求：

生成n对括号的所有组合
每个组合都必须是有效的括号序列
输出不能有重复组合

示例：输入：n = 3 输出：[”((()))”, ”(()())”, ”(())()”, ”()(())”, ”()()()”]

😱 常见误区大揭秘#

无脑回溯：不加约束生成所有可能组合，产生大量无效序列
忽视平衡性：没有控制左右括号数量关系，导致非法组合
终止条件混淆：不清楚何时应该停止添加括号

就像写代码时随意输入括号，最后发现一堆语法错误！

🚀 优雅的解题思路#

核心算法：回溯 + 平衡约束#

// 主函数：生成 n 对括号的所有合法组合
public List<String> generateParenthesis(int n) {
    // result：保存最终所有有效括号字符串
    List<String> result = new ArrayList<>();
    // 从空字符串开始回溯：
    // open 表示已使用左括号数量
    // close 表示已使用右括号数量
    // max 为目标对数 n
    backtrack(result, "", 0, 0, n);
    // 返回所有合法组合
    return result;
}

// 回溯函数：在 current 基础上继续添加括号
private void backtrack(List<String> result, String current, 
                      int open, int close, int max) {
    // 终止条件：当长度达到 2 * n 时，说明已经放满 n 对括号
    if (current.length() == max * 2) {
        // 此时 current 一定是合法组合（因为扩展过程始终受约束）
        result.add(current);
        // 当前分支结束
        return;
    }

    // 选择 1：尝试添加左括号
    // 条件：已用左括号数 open 还没达到上限 max
    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }

    // 选择 2：尝试添加右括号
    // 条件：右括号数 close 必须小于左括号数 open，保证前缀始终合法
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

java

算法思维图解#

状态跟踪：实时记录已使用的左括号(open)和右括号(close)数量
关键约束：
- 左括号数量不超过n
- 右括号数量不超过左括号数量
决策过程：在每一步都面临两个选择：
- 添加左括号？
- 添加右括号？

就像编辑器的实时语法检查：

输入左括号时检查是否达到上限
输入右括号时确保有未匹配的左括号
达到期望长度时完成一个组合

🏆 效率优化要点#

空间优化：使用StringBuilder替代String拼接
提前剪枝：通过括号计数快速判断无效路径
递归优化：避免创建过多String对象

💼 面试必问三连击#

为什么要跟踪open和close？
- 保证括号序列的合法性
- 控制生成过程中的平衡约束
如何保证不重复生成？
- 通过严格的生成顺序：优先考虑左括号
- 利用回溯过程中的约束条件自然去重
能否用其他方法解决？
- 动态规划方案
- 深度优先搜索
- 按位枚举（但不推荐）

📌 解题技巧总结#

把握三个核心要点：

平衡原则：右括号数不超过左括号
计数约束：左右括号各n个
回溯思维：在保证合法性的前提下尝试所有可能