5分钟彻底掌握括号生成题！用「栈匹配理论」轻松理解

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

📝 从生活场景说起

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

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

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

💡 题目解析

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

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

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

😱 常见误区大揭秘

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

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

🚀 优雅的解题思路

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

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

private void backtrack(List<String> result, String current, 
                      int open, int close, int max) {
    // 找到有效组合
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }
    
    // 可以添加左括号的条件：未使用的左括号数量大于0
    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }
    
    // 可以添加右括号的条件：已使用的右括号少于左括号
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

算法思维图解

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

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

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

🏆 效率优化要点

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

💼 面试必问三连击

1. 为什么要跟踪open和close？

   • 保证括号序列的合法性
   • 控制生成过程中的平衡约束

2. 如何保证不重复生成？

   • 通过严格的生成顺序：优先考虑左括号
   • 利用回溯过程中的约束条件自然去重

3. 能否用其他方法解决？

   • 动态规划方案
   • 深度优先搜索
   • 按位枚举（但不推荐）

📌 解题技巧总结

把握三个核心要点：

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

---

作者：忍者算法 公众号：忍者算法

🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步

#算法面试 #LeetCode #回溯算法 #括号匹配