括号生成 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2

输入：n = 1

输出：["()"]

💭 模拟答题者思考

1. 我先想暴力：枚举所有长度为 2n 的 '('/')' 组合，再逐个用栈判断是否合法——思路对，但组合数高达 2^{2n}，大量无效串被白白生成。

2. 重复在哪里？每多放一个括号，子问题变成「在已有前缀上继续补全剩余括号」；无效分支的共同特征是：某一时刻右括号比左括号多，或左括号已经用完却还在放左括号。

3. 优化成回溯剪枝：用 open、close 记录已用括号数；能放 '(' 当且仅当 open < n，能放 ')' 当且仅当 close < open。

4. 终止条件：len(path) == 2n 时得到一棵完整合法串，加入 ans；否则按「先尝试左、再尝试右」递归，每次选择后撤销。

5. n = 1 只有 "()"；n 最大为 8，回溯深度 ≤ 16，剪枝后实际访问节点远少于全枚举。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`path`	str / list	定义：当前已拼接的括号前缀维护：每次递归尝试在末尾追加 `'('` 或 `')'` 更新：选左括号时追加并递归；回溯时撤销（`pop` 或切片还原）
`open`	int	定义：`path` 中已使用的左括号 `'('` 个数维护：只有 `open < n` 时才允许再追加左括号更新：追加 `'('` 时 `open++`；回溯返回后恢复
`close`	int	定义：`path` 中已使用的右括号 `')'` 个数维护：只有 `close < open` 时才允许追加右括号（保证任意前缀合法）更新：追加 `')'` 时 `close++`；回溯返回后恢复
`ans`	list<str>	定义：所有长度为 `2n` 的合法括号串维护：当 `len(path) == 2n` 时，将当前 `path` 的副本加入更新：每到达叶子层追加一次；中途不收集半成品

⌨️ 落码步骤

1. 初始化结果列表 ans，定义 DFS backtrack(path, open, close)

2. 若 len(path) == 2 * n，将 path 加入 ans 并返回

3. 若 open < n：追加 '('，递归 backtrack(..., open+1, close)，再撤销

4. 若 close < open：追加 ')'，递归 backtrack(..., open, close+1)，再撤销

5. 从 backtrack([], 0, 0) 启动，返回 ans

💻 代码实现

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans: list[str] = []

        def backtrack(path: list[str], open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                ans.append("".join(path))
                return
            if open_cnt < n:
                path.append("(")
                backtrack(path, open_cnt + 1, close_cnt)
                path.pop()
            if close_cnt < open_cnt:
                path.append(")")
                backtrack(path, open_cnt, close_cnt + 1)
                path.pop()

        backtrack([], 0, 0)
        return ans

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;

        function<void(int, int)> dfs = [&](int open, int close) {
            if ((int)path.size() == 2 * n) {
                ans.push_back(path);
                return;
            }
            if (open < n) {
                path.push_back('(');
                dfs(open + 1, close);
                path.pop_back();
            }
            if (close < open) {
                path.push_back(')');
                dfs(open, close + 1);
                path.pop_back();
            }
        };

        dfs(0, 0);
        return ans;
    }
};
// 时间 O(4^n / √n)，空间 O(n)（递归栈，不计输出）

📈 复杂度分析

时间复杂度 O(4^n / √n)

空间复杂度 O(n)（递归栈，不计输出）

⚠️ 常见坑

❗ 右括号放太早：必须满足 close < open 才能追加 ')'，否则会出现 ")(" 这类非法前缀。

❗ 回溯不撤销：追加括号后递归返回，必须 pop，否则 path 会污染兄弟分支。

❗ 终止条件写错：应判断 len(path) == 2*n（或 open == close == n），不能只判断 open == n 就收集——那时右括号还没补全。

🔍 必测边界 Case

Case 1：n = 1

n = 1 → ["()"]

Case 2：n = 2

n = 2 → ["(())","()()"]（共 2 种）

Case 3：n = 3

n = 3 → 5 种合法串（卡特兰数 C₃ = 5）