括号生成 图解题解
n 对括号的合法组合，不用枚举再筛——两条规矩边生成边剪枝，连废串都不会产生。
像填空题的监考老师：不等学生写完再全部批改，而是边写边看——只要当前草稿已经出现「右括号比左括号多」这种先天残疾，直接没收试卷、这条路作废。剩下的题目只让两类人往下走：左括号没用完的，还能再放左；已放右括号少于左括号的，才能放右。守住这两条规矩，树上每条枝头长出来的就一定是合法括号，不需要事后筛垃圾。
这道题到底在问什么
- n
- 3
- 输出
- ((())) (()()) (())() ()(()) ()()()
最优解：一步一步想明白
- 3把所有 ( 和 ) 的排列都生成出来(n=3 就是 2^6=64 个)再挑合法的，绝大多数都是 "())( " 这种废串，白生成。
- 4转折：把「合法」翻译成「什么时候能往下放」。构建过程中只要发现这一步会让前缀非法，立刻掐断这条分支，连试都不试，省掉所有废串。
- 5两条规则（left/right = 已经放了几个左/右括号）：左括号没放满(left 小于 n)就能放 (；已放的右括号比左括号少(right 小于 left)才能放 )。守住这两条，生成的一定合法。
- 6剪枝规则：left 没满(小于 n)才能放 (；right 比 left 少才能放 )。开局 left=right=0，放 ) 会先冒出右括号、非法 → 只能放 (。
- 7能放左就先放左，直到 left=3=n。此刻 left 已满，不能再放 (，只能开始补右括号。
- 8左满后依次补 3 个 )，长度到 2n=6 → 第一条结果 ((())) 收集。
- 9回溯退回到前缀 ((，这次改放 )（right=0 比 left=2 少，允许放右）→ 新前缀 (()。剪枝条件决定了每一步能往哪走。
- 10从 (() 继续：放 ( 再补右 → 第二条 (()())。
- 11继续回溯尝试其它合法前缀，依次得到 (())()、()(())、()()()。n=3 共 5 条（卡特兰数 C₃=5）。
- 14回溯类题的通用思路：把「什么时候合法」翻译成「什么时候能往下放」，不合法的分支直接不进，效率天差地别。
- 19把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：放 ) 的条件写成 right 大于 0
✓ 对：right 小于 left（右比左少才能再放）
合法串任意前缀里 ( 数不少于 ) 数。只有已放的 ) 比 ( 少才能再放 )；写成 right 大于 0 会在 () 后再补一个 ) 拼出 ()) 这类非法串。
✗ 错：收结果时直接存 path 引用
✓ 对：存 "".join(path) 或 path[:] 的快照
path 后面还会被 pop/修改，存引用会让结果列表里的每一项都变成最后那条
✗ 错：用 path + ["("] 之外还手动回溯
✓ 对：二选一：要么传新列表、要么 append 后 pop
混用会重复撤销，路径乱套
完整代码（Python / C++ / Java）
Python
class Solution:
def generateParenthesis(self, n):
ans = []
def backtrack(path, left, right):
if len(path) == 2 * n:
ans.append(''.join(path))
return
if left < n:
path.append('(')
backtrack(path, left + 1, right)
path.pop()
if right < left:
path.append(')')
backtrack(path, left, right + 1)
path.pop()
backtrack([], 0, 0)
return ansC++
class Solution {
public:
vector<string> ans;
int n;
void backtrack(string& path, int left, int right) {
if ((int)path.size() == 2 * n) { ans.push_back(path); return; }
if (left < n) { // 左没满才能放 (
path.push_back('(');
backtrack(path, left + 1, right);
path.pop_back();
}
if (right < left) { // 右比左少才能放 )
path.push_back(')');
backtrack(path, left, right + 1);
path.pop_back();
}
}
vector<string> generateParenthesis(int n) {
this->n = n;
string path;
backtrack(path, 0, 0);
return ans;
}
};Java
class Solution {
List<String> ans = new ArrayList<>();
int n;
void backtrack(StringBuilder path, int left, int right) {
if (path.length() == 2 * n) { ans.add(path.toString()); return; }
if (left < n) { // 左没满才能放 (
path.append('(');
backtrack(path, left + 1, right);
path.deleteCharAt(path.length() - 1);
}
if (right < left) { // 右比左少才能放 )
path.append(')');
backtrack(path, left, right + 1);
path.deleteCharAt(path.length() - 1);
}
}
public List<String> generateParenthesis(int n) {
this.n = n;
backtrack(new StringBuilder(), 0, 0);
return ans;
}
}套路模板 · 回溯生成（背下来）
def bt(path, 状态):
if 到达终点:
res.append(path 的快照); return
for 每个合法选择:
做选择（更新 path 和状态）
bt(path, 新状态)
撤销选择（回溯）void bt(Path& path, State st) {
if (到达终点) { // 长度=2n
res.push_back(path 的快照); return;
}
for (每个合法选择) { // 受剪枝约束
做选择; // 更新 path 和 st
bt(path, 新状态);
撤销选择; // 回溯 pop
}
}void bt(Path path, State st) {
if (到达终点) { // 长度=2n
res.add(path 的快照); return;
}
for (每个合法选择) { // 受剪枝约束
做选择; // 更新 path 和 st
bt(path, 新状态);
撤销选择; // 回溯 pop
}
}复杂度
时间复杂度
第 n 个卡特兰数
合法串约 4ⁿ/(n√n) 个，每个拼接花 O(n)，靠剪枝只走合法分支
空间复杂度
O(n)
递归深度最多 2n，path 也最多 2n 长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 括号生成 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 close＜open 才能加右括号？+
保证任意前缀左括号数≥右括号数，这正是合法括号串的充要条件。
一共多少种结果？+
卡特兰数 C(n)；时间约 O(4^n/√n)。
和「生成所有 2^(2n) 再筛」有何不同？+
回溯在生成时就剪枝、只走合法前缀，省掉绝大多数非法分支。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。