括号生成
Generate Parentheses
生成所有由 n 对括号组成的合法括号串。
在力扣中练习题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
解题思路
主解法
回溯 · 左右括号计数
左括号没用完就能放左，右括号少于左才能放右
合法括号串有两个必要条件：左括号总数不超过 n；任何前缀里右括号数量不超过左括号。
把这两个条件直接写进递归：只要 open < n 就可以放左括号；只要 close < open 就可以放右括号。长度达到 2n 时自然是一个合法串。
分步图解
n=3：最终长度 6；open 最多到 n，close 任何时刻都不能超过 open。
这样不需要生成所有 2^(2n) 种括号组合再筛选，非法前缀在产生时就被剪掉了。
分步图解
长度达到 6，()(()) 是一个合法串，加入 res。
- res.size
- 4
自拟 n=3，共 5 个解。注意先放左括号的分支会一直深到底，再通过回退改变左右顺序；画面上 path 和两个计数器始终满足不变量。
时间复杂度是第 n 个卡特兰数，约 O(4ⁿ/√n)；递归深度 O(n)。
时间 O(4ⁿ/√n)空间 O(n)
易错点
- 只限制 open <= n，不限制 close < open：会产生 ()) 这类非法前缀。
- 先放右括号再放左括号：顺序不同但仍可能生成重复串。
- 终止条件写成 open == n：会漏掉还没补完右括号的串。
对照解法
暴力枚举 · 后验证
先枚举所有括号串，再判断是否合法
会生成 2^(2n) 个候选串，再逐个 O(n) 验证，远慢于剪枝回溯；仅作对照。
每一层都可以放左或右，递归生成全部 2^(2n) 个串；到叶子后用栈或计数器验证是否合法。
这种写法最容易理解，但绝大多数分支从一开始就非法，仍然会被完整生成和验证。
它适合用来验证剪枝版的正确性，不适合作为提交答案。
- 1每一步都尝试左括号和右括号。
- 2长度到 2n 时验证。
- 3验证通过加入结果。
时间 O(2^(2n)·n)空间 O(n)
易错点
- 验证时只数总数相等：会漏掉前缀非法的串。
- 递归拼接字符串：额外复制开销大。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
n = 3n=3：最终长度 6；open 最多到 n，close 任何时刻都不能超过 open。
查看 C++ 代码
延伸阅读
- 合法括号的计数是卡特兰数；剪枝版只走合法前缀，复杂度与结果数量同阶。
- 括号类问题常把“数量约束”和“前缀约束”分别写成两个 if，而不是统一用栈。