题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于生成所有可能并且有效的括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]提示：1 <= n <= 8
解题思路总览
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 回溯 | O(4^n / sqrt(n)) | O(n) | 经典解法，指数级 |
| 动态规划 | O(n^2) | O(n^2) | 卡特兰数递推 |
| BFS | O(4^n / sqrt(n)) | O(4^n) | 逐层构建 |
为什么用回溯？
- 括号生成本质是「在每个位置选择左或右」
- 必须保证有效性（右括号不能多于左括号）
- 需要枚举所有可能的有效组合
完整代码
classSolution{public:vector<string>generateParenthesis(intn){vector<string>ans;stringpath(2*n,0);// 预分配长度为2n的字符串autotraversal=[&](thisauto&&traversal,intleft,intright)->void{if(right==n){ans.push_back(path);return;}// 可以放左括号if(left<n){path[left+right]='(';traversal(left+1,right);}// 可以放右括号（不能比左括号多）if(right<left){path[left+right]=')';traversal(left,right+1);}};traversal(0,0);returnans;}};算法流程图
[开始] | [初始化 ans, path] | [递归 traversal(0, 0)] | [right == n?] | / 是 \ / 否 / \ 保存结果 [left < n?] 返回 | / 是 \ / 否 / \ [放左括号] [跳过左] path[pos]='(' | 递归 left+1 | [right < left?] | / 是 \ / 否 / \ [放右括号] [跳过右] path[pos]=')' 递归 right+1 | [返回]决策树图解（n=2）
[根: left=0, right=0, pos=0] | +---------+---------+ | | 放 '(' （不放左，继续） left=1 | pos=1 | | right < left? | yes -> 放 ')' | right=1, pos=1 [left=1,right=0] | | [left=1,right=1] | | +-------+-------+ | | | | 放 '(' 放 ')' 放 ')' left=2 right<left right=2 == n pos=2 yes ans: "(())" | | [left=2,right=0] [left=1,right=1] | | 放 ')' 放 ')' right=1 right=2 == n pos=2 ans: "()()" | [left=2,right=1] | 放 ')' right=2 == n ans: "(())" 最终结果: ["(())", "()()"]逐行解析
1. 预分配字符串
stringpath(2*n,0);- 长度为
2*n的字符串，所有位置初始化为\0 - 用位置索引
left + right直接访问，O(1) 写入
2. C++23 新语法解析
autotraversal=[&](thisauto&&traversal,intleft,intright)->void{this auto && traversal是 C++23 的显式 lambda 模板参数this表示它是成员函数式的调用（可以递归）- 等价于普通写法：
function<void(int,int)>traversal=[&](intleft,intright){// ...};- 或者经典写法：
voidtraversal(intleft,intright){if(right==n){...}if(left<n){path[left+right]='(';traversal(left+1,right);}if(right<left){path[left+right]=')';traversal(left,right+1);}}3. 终止条件
if(right==n){ans.push_back(path);return;}right == n表示 n 个右括号都用完了- 此时
left也必然等于 n（因为 right <= left） - 这就是一组有效的括号组合
4. 放左括号
if(left<n){path[left+right]='(';traversal(left+1,right);}left < n表示还有左括号可用- 当前位置 =
left + right（已放 left 个左，right 个右） - 放完后递归，left+1
5. 放右括号（关键合法性检查）
if(right<left){path[left+right]=')';traversal(left,right+1);}right < left保证：右括号数量永远不会超过左括号- 这是括号有效性的核心保证
- 如果没有这个检查，会产生
)(这种非法情况
详细 trace 演示（n=2）
初始: path = "____", left=0, right=0 traversal(0, 0): right(0) < n(2)? 否，不终止 left(0) < n(2)? 是 path[0] = '(' traversal(1, 0) right(0) < left(0)? 否，不放右 traversal(1, 0): left<2: path[1]='(', traversal(2, 0) right<left? 0<1? 是, path[1]=')', traversal(1, 1) traversal(2, 0): left<2? 否 right<left? 0<2? 是, path[2]=')', traversal(2, 1) traversal(2, 1): left<2? 否 right<left? 1<2? 是, path[3]=')', traversal(2, 2) traversal(2, 2): right == n, ans.push_back("(())") traversal(1, 1): left<2? 是, path[2]='(', traversal(2, 1) right<left? 1<1? 否 traversal(2, 1): right<left? 1<2? 是, path[3]=')', traversal(2, 2) traversal(2, 2): right == n, ans.push_back("()()") 最终结果: ["(())", "()()"]复杂度分析
时间复杂度：O(4^n / sqrt(n))
- 卡特兰数，第 n 个括号组合数
- 精确值 = C(2n, n) / (n + 1) ≈ 4^n / (n^(3/2) * sqrt(pi))
| n | 组合数 | 说明 |
|---|---|---|
| 1 | 1 | () |
| 2 | 2 | (()), ()() |
| 3 | 5 | ((())), (()()), (())(), ()(()), ()()() |
| 4 | 14 | … |
| 5 | 42 | … |
| 8 | 1430 | … |
空间复杂度：O(n)
- 递归栈最大深度 = 2n
- path 字符串长度 = 2n
常见错误
错误1：合法性检查写错
// 错误：写成 right <= left 会允许 right == leftif(right<=left){path[left+right]=')';traversal(left,right+1);}// 正确：右括号必须严格少于左括号才能放if(right<left){path[left+right]=')';traversal(left,right+1);}错误2：终止条件写错
// 错误：写成 left == n 不够if(left==n){ans.push_back(path);return;}// 问题：如果 right < left，还没放完右括号就提前返回了// 正确：必须右括号用完才算完成if(right==n){ans.push_back(path);return;}错误3：位置计算错误
// 错误：只用 right 当位置path[right]='(';traversal(left,right+1);// 正确：用 left + right 当位置path[left+right]='(';traversal(left+1,right);面试追问 FAQ
| 问题 | 回答 |
|---|---|
| 为什么 right < left 而不是 right <= left？ | 右括号必须严格少于左括号才能放，否则会出现)(的非法情况。比如(()可以放右，但()(不能放右 |
| 能不用递归吗？ | 可以用迭代，但递归最直观，n 最大才 8，递归深度可控 |
| 卡特兰数是什么？ | 括号组合数是第 n 个卡特兰数 C(2n,n)/(n+1)，这是典型的卡特兰数应用 |
| 如何按字典序输出？ | 题目通常不要求，但可以先放左再放右得到字典序 |
| 如何判断括号有效性？ | 本题本身就是验证，但可以用栈：左括号入栈，右括号出栈检查匹配 |
相关题目对比
| 题目 | 难度 | 核心区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 验证括号是否合法（栈） |
| 32. 最长有效括号 | 困难 | 最长合法子串长度 |
| 241. 为运算表达式加括号 | 中等 | 给表达式加括号改变优先级 |
| 678. 有效的括号字符串 | 中等 | 判断是否有合法括号串（含 * 号） |
举一反三
什么时候用回溯？
- 问题的解空间是树状结构
- 每个节点有多个分支选择
- 需要枚举所有可能的解
括号问题的通用模式：
放左括号的条件：left < n 放右括号的条件：right < left 终止条件：right == n卡特兰数应用场景：
| 场景 | 说明 |
|---|---|
| 括号生成 | 本题 |
| 二叉树结构计数 | n 个节点的不同二叉树数 |
| 买卖股票问题 | 含冷冻期的交易次数 |
| 出栈顺序问题 | n 个元素的不同出栈序列数 |
总结
| 要点 | 说明 |
|---|---|
| 核心思想 | 回溯 + 合法性检查 |
| 关键条件 | 放右括号：right < left |
| 终止条件 | right == n |
| 位置计算 | left + right |
| 时间复杂度 | O(4^n / sqrt(n))，卡特兰数 |
| 空间复杂度 | O(n) |
| C++23 语法 | this auto && traversal显式 lambda 模板参数 |
完整测试代码
#include<iostream>#include<vector>#include<string>usingnamespacestd;classSolution{public:vector<string>generateParenthesis(intn){vector<string>ans;stringpath(2*n,0);autotraversal=[&](thisauto&&traversal,intleft,intright)->void{if(right==n){ans.push_back(path);return;}if(left<n){path[left+right]='(';traversal(left+1,right);}if(right<left){path[left+right]=')';traversal(left,right+1);}};traversal(0,0);returnans;}};intmain(){Solution s;for(intn=1;n<=3;n++){cout<<"n = "<<n<<":"<<endl;vector<string>ans=s.generateParenthesis(n);cout<<"[";for(inti=0;i<ans.size();i++){cout<<"\""<<ans[i]<<"\"";if(i<ans.size()-1)cout<<", ";}cout<<"]"<<endl<<endl;}return0;}运行结果：
n = 1: ["()"] n = 2: ["(())", "()()"] n = 3: ["((()))", "(()())", "(())()", "()(())", "()()()"]
