题目链接 · 灵神原题解（署名来源）

分析

本质上来说，我们需要在 $0,1,2,\dots ,2n-1$ 中选 $n$ 个数（位置），填入左括号。其余 $n$ 位置填入右括号。

所以本题其实就是 77. 组合。但有额外约束，对于括号字符串的任意前缀，右括号的个数不能超过左括号的个数。比如 $\mathtt{\text{())(}}$ 是不合法的。

具体请看视频讲解：组合型回溯+剪枝【基础算法精讲 15】。制作不易，欢迎点赞~

方法一：枚举当前位置填左括号还是右括号

本质是「选或不选」的思想，你可以把填左括号视作「选」，填右括号视作「不选」。

递归的过程中，要保证右括号的个数不能超过左括号的个数。

如果现在右括号个数等于左括号个数，那么不能填右括号。

如果现在右括号个数小于左括号个数，那么可以填右括号。

由于左括号个数始终 $\ge$ 右括号个数，且至多填 $n$ 个左括号，所以当我们填了 $n$ 个右括号时，也一定填了 $n$ 个左括号，此时填完所有 $2n$ 个括号。

答疑

问：什么时候需要写恢复现场，什么时候不需要写？

答：下面代码中，如果初始化 $\mathit{\text{path}}$ 为空列表，就需要写恢复现场。本题由于所有括号长度都是固定的 $2n$，我们可以创建一个长为 $2n$ 的 $\mathit{\text{path}}$ 列表，在递归时直接写入字符（而不是插入字符），这样做无需写恢复现场。

问：代码如何保证 $\mathit{\text{path}}[0]$ 一定是左括号，$\mathit{\text{path}}[2n-1]$ 一定是右括号？

答：一开始 $\mathit{\text{left}}=\mathit{\text{right}}=0$，填右括号的那个 $\mathtt{\text{if}}$ 条件不成立，所以 $\mathit{\text{path}}[0]$ 只能填左括号。由于只有在 $\mathit{\text{right}}<\mathit{\text{left}}$ 时才能填右括号，当 $\mathit{\text{right}}=\mathit{\text{left}}$ 时 $\mathit{\text{right}}$ 不能再变大，所以始终有 $\mathit{\text{right}}\le \mathit{\text{left}}$。当我们填了 $2n-1$ 个括号时，唯一解是 $\mathit{\text{left}}=n$ 且 $\mathit{\text{right}}=n-1$，此时填左括号的那个 $\mathtt{\text{if}}$ 条件不成立，所以 $\mathit{\text{path}}[2n-1]$ 只能填右括号。

Python 解法1

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = [''] * (n * 2)  # 所有括号长度都是 2n

        # 目前填了 left 个左括号，right 个右括号
        def dfs(left: int, right: int) -> None:
            if right == n:  # 填完 2n 个括号
                ans.append(''.join(path))
                return
            if left < n:  # 可以填左括号
                path[left + right] = '('  # 直接覆盖
                dfs(left + 1, right)
            if right < left:  # 可以填右括号
                path[left + right] = ')'  # 直接覆盖
                dfs(left, right + 1)

        dfs(0, 0)  # 一开始没有填括号
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path(n * 2, 0); // 所有括号长度都是一样的 2n

        // 目前填了 left 个左括号，right 个右括号
        auto dfs = [&](this auto&& dfs, int left, int right) -> void {
            if (right == n) { // 填完 2n 个括号
                ans.emplace_back(path);
                return;
            }
            if (left < n) { // 可以填左括号
                path[left + right] = '('; // 直接覆盖
                dfs(left + 1, right);
            }
            if (right < left) { // 可以填右括号
                path[left + right] = ')'; // 直接覆盖
                dfs(left, right + 1);
            }
        };

        dfs(0, 0); // 一开始没有填括号
        return ans;
    }
};

复杂度分析

• 时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度$\times$搜索树的叶子数。对于本题，它等于 $\mathcal{O}(n\cdot C(2n,n))$。但由于左右括号的约束，实际上没有这么多叶子，根据 Catalan 数，只有 ${\displaystyle \frac{C(2n,n)}{n+1}}$ 个叶子节点，所以实际的时间复杂度为 $\mathcal{O}(C(2n,n))$。此外，根据阶乘的 Stirling 公式，时间复杂度也可以表示为 $\mathcal{O}\left({\displaystyle \frac{4^n}{\sqrt{n}}}\right)$。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计入。

方法二：枚举下一个左括号的位置

用「枚举选哪个」的思路。

在从左往右填的过程中，要时刻保证右括号的个数不能超过左括号的个数。

如果前面填了 $5$ 个左括号，$2$ 个右括号，那么还能填几个右括号？

至多填 $5-2=3$ 个。

所以枚举（在填下一个左括号之前）填入了 $0,1,2,3$ 个右括号，这样就能得到下一个左括号的位置。

为了方便，代码直接用 $\mathit{\text{balance}}$ 表示左右括号之差。这样我们枚举的范围就是 $[0,\mathit{\text{balance}}]$。

注意最后一个左括号的右边还可以填右括号，但无需考虑。填入所有左括号后，剩余的位置我们会自动填入右括号。

Python 解法3

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = []  # 记录左括号的下标

        # 目前填了 i 个括号
        # balance = 这 i 个括号中的左括号个数 - 右括号个数
        def dfs(i: int, balance: int) -> None:
            if len(path) == n:
                s = [')'] * (n * 2)
                for j in path:
                    s[j] = '('
                ans.append(''.join(s))
                return
            # 枚举填 right=0,1,2,...,balance 个右括号
            for right in range(balance + 1):
                # 先填 right 个右括号，然后填 1 个左括号，记录左括号的下标 i+right
                path.append(i + right)
                dfs(i + right + 1, balance - right + 1)
                path.pop()  # 恢复现场

        dfs(0, 0)
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        vector<int> path; // 记录左括号的下标

        // 目前填了 i 个括号
        // 这 i 个括号中的左括号个数 - 右括号个数 = balance
        auto dfs = [&](this auto&& dfs, int i, int balance) {
            if (path.size() == n) {
                string s(n * 2, ')');
                for (int j : path) {
                    s[j] = '(';
                }
                ans.emplace_back(s);
                return;
            }
            // 枚举填 right=0,1,2,...,balance 个右括号
            for (int right = 0; right <= balance; right++) {
                // 先填 right 个右括号，然后填 1 个左括号，记录左括号的下标 i+right
                path.push_back(i + right);
                dfs(i + right + 1, balance - right + 1);
                path.pop_back(); // 恢复现场
            }
        };

        dfs(0, 0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度$\times$搜索树的叶子数。对于本题，它等于 $\mathcal{O}(n\cdot C(2n,n))$。但由于左右括号的约束，实际上没有这么多叶子，根据 Catalan 数，只有 ${\displaystyle \frac{C(2n,n)}{n+1}}$ 个叶子节点，所以实际的时间复杂度为 $\mathcal{O}(C(2n,n))$。此外，根据阶乘的 Stirling 公式，时间复杂度也可以表示为 $\mathcal{O}\left({\displaystyle \frac{4^n}{\sqrt{n}}}\right)$。
• 空间复杂度：$\mathcal{O}(n)$。返回值的空间不计入。

思考题

如果可以填小括号中括号大括号呢？（例子见 20. 有效的括号）

欢迎在评论区分享你的思路/代码。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府