几年前我准备求职时，也曾一头扎进 LeetCode 的题海。从最初的“看题懵圈”到后来能在面试中从容写出最优解，每天坚持刷一道题成了我提升算法能力最有效的方式。那段经历不仅帮我顺利拿到心仪 offer，更让我养成了系统思考和高效编码的习惯。
如今工作稳定了，终于有时间把当年的刷题笔记重新整理、优化，并用 Python 语言 逐题讲解清楚。希望能帮助正在准备面试、转行或想夯实基础的你——少走弯路，高效进步。
关键词：回溯、DFS、括号生成、合法性剪枝、递归
难度：中等
推荐指数：⭐⭐⭐⭐⭐（高频回溯题，考察构造与约束建模）
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
有效括号需满足：
- 每个左括号 '(' 必须有对应的右括号 ')'
- 左右括号顺序必须合法（任意前缀中左括号数 ≥ 右括号数）
示例
输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
输入: n = 1
输出: ["()"]
约束条件
- 1 <= n <= 8
解题思路
本题要求生成所有合法的括号序列，属于典型的构造型回溯问题。
暴力枚举所有 2n 长度的 '('/')' 组合（共 2^(2n) 种），再验证合法性，效率极低。
我们需要在构造过程中就保证合法性，即边生成边剪枝。
合法性核心观察：
一个括号序列合法，当且仅当：
这意味着：不能先放右括号，且右括号数量不能超过左括号
回溯状态设计：
我们用递归函数维护以下状态：
- left：已使用的左括号数量
- right：已使用的右括号数量
- path：当前构建的字符串（或字符列表）
选择与约束：
- 可加 '(' 的条件：left < n
- 可加 ')' 的条件：right < left（确保不会出现 )( 类非法结构）
终止条件：
- len(path) == 2 * n → 加入结果集
这种“按规则生成”的方式天然避免无效组合，大幅剪枝！
Python 代码实现（含逐层递归解析）
解法：回溯（DFS）｜带合法性剪枝
class Solution:
def generateParenthesis(self, n: int) –> List[str]:
result = []
def backtrack(left, right, path):
# 终止条件：已生成 2n 个括号
if len(path) == 2 * n:
result.append(''.join(path))
return
# 尝试添加左括号（只要还没用完 n 个）
if left < n:
path.append('(')
backtrack(left + 1, right, path)
path.pop() # 回溯
# 尝试添加右括号（只有当右括号数 < 左括号数时才合法）
if right < left:
path.append(')')
backtrack(left, right + 1, path)
path.pop() # 回溯
backtrack(0, 0, [])
return result
超详细逐层逻辑解析
初始调用：backtrack(0, 0, [])
- 尚未使用任何括号，路径为空。
左括号分支：if left < n
- 只要左括号没用完（最多 n 个），就可以放。
- 例如 n=2，第一步必选 '('（因为 right < left 不成立，不能先放 ')'）。
右括号分支：if right < left
- 这是合法性剪枝的关键！
- 保证任何时候右括号数量不超过左括号，从而避免如 "())(" 或 "())" 等非法前缀。
为什么这样能覆盖所有合法组合？
- 所有合法序列都满足：每一步要么加 '('（若还能加），要么加 ')'（若合法）。
- 回溯会穷举所有满足这两个条件的路径，且只生成合法序列。
示例：n = 2 的递归树（简化）
""
/
"("
/ \\
"((" "()"
/ \\
"(()" "()("
/ \\
"(() )" "()()"
- 每条叶子路径都是合法结果："(())", "()()"
注意：")(" 在第一步就被禁止（因 right=0 不小于 left=0），根本不会生成。
复杂度分析
| 时间复杂度 | O(4ⁿ / √n) |
| 空间复杂度 | O(n)（递归栈深度为 2n） |
实际生成的组合数为 第 n 个卡特兰数：Cₙ = (1/(n+1)) * C(2n, n) ≈ 4ⁿ / (n√n)
本题 n ≤ 8，最大输出 1430 个字符串，完全可接受。
小结 & 面试技巧
- 核心思想：在构造过程中通过约束保证合法性
- 两大剪枝条件：
- 左括号最多 n 个
- 右括号数不能超过左括号数
- 常见错误：
- 先生成再验证（超时）
- 忘记 right < left 条件，导致生成非法序列
- 用字符串拼接而非列表（效率低）
- 面试话术：
“我使用回溯法，在每一步决策时只添加合法的括号。具体来说，只要左括号没用完就可以加；而右括号只有在当前数量少于左括号时才能加。这样生成的所有序列天然合法，无需后验检查。”
- 扩展思考：
- 若允许 * 作为通配符（可代表 '('、')' 或空），如何判断是否能构成有效括号？（LeetCode #678）
- 如何按字典序输出结果？（本解法天然按 '(' 优先，已是字典序）
下期预告
明天我们将挑战第 23 题：合并 K 个升序链表，带你用分治与最小堆两种策略高效解决多路归并难题！
坚持每天一道 LeetCode，用 Python 写出优雅代码，夯实算法基础，拿下心仪 Offer！
关注专栏，不错过每日更新！
