括号生成

题意

给定整数 $n$ ，生成所有由 $n$ 对括号组成的合法括号组合。

合法括号组合要求：任意前缀中左括号数量 $\geqslant$ 右括号数量，且最终两者相等。

思路

最直接的思路是枚举所有长度为 $2n$ 的括号序列，逐一检查合法性：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46// brute.cpp：小数据暴力解，01 序列递归枚举所有括号序列，叶子节点检查合法性。
#include <bits/stdc++.h>
using namespace std;

int n;
int choose[20]; // 0 = '(' , 1 = ')'
vector<string> ans;

bool check() {
    int bal = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (choose[i] == 0)
            bal++;
        else
            bal--;
        if (bal < 0)
            return false;
    }
    return bal == 0;
}

void dfs(int dep) {
    if (dep == 2 * n + 1) {
        if (check()) {
            string s;
            for (int i = 1; i <= 2 * n; i++)
                s += (choose[i] == 0 ? '(' : ')');
            ans.push_back(s);
        }
        return;
    }
    choose[dep] = 0;
    dfs(dep + 1);
    choose[dep] = 1;
    dfs(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    for (auto &s : ans)
        cout << s << '\n';
    return 0;
}

这个暴力先生成完整序列再到叶子节点检查合法性。它在小数据上可靠，但分支数为 $2^{2n}$ ，对 $n \geqslant 8$ 就会超时。

优化的关键是剪枝：不等到序列完成后再检查，而是在每一步就保证前缀合法。

open < n 时可以放左括号——左括号总数不能超过 $n$ 。
close < open 时可以放右括号——任意前缀中右括号不能多于左括号。

这两个条件保证每一步之后前缀仍然合法，因此最终到达叶子时一定是一个合法组合，且所有合法组合都会被访问到。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string cur;
        function<void(int, int)> dfs = [&](int open, int close) {
            if (open == n && close == n) {
                ans.push_back(cur);
                return;
            }
            if (open < n) {
                cur.push_back('(');
                dfs(open + 1, close);
                cur.pop_back();
            }
            if (close < open) {
                cur.push_back(')');
                dfs(open, close + 1);
                cur.pop_back();
            }
        };
        dfs(0, 0);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (auto &s : Solution().generateParenthesis(n))
        cout << s << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
from typing import List


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

        def dfs(open, close):
            if open == n and close == n:
                ans.append("".join(cur))
                return
            if open < n:
                cur.append("(")
                dfs(open + 1, close)
                cur.pop()
            if close < open:
                cur.append(")")
                dfs(open, close + 1)
                cur.pop()

        dfs(0, 0)
        return ans


def main():
    n = int(input())
    for s in Solution().generateParenthesis(n):
        print(s)


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(C_n)$ ，其中 $C_n = \frac{1}{n+1}\binom{2n}{n}$ 是 Catalan 数，即合法组合的数量。每个组合需要 $2n$ 步构建。
空间复杂度： $O(n)$ ，递归栈深度为 $2n$ 。

总结

括号生成是 Catalan 数的经典应用。关键剪枝条件 close < open 保证任意前缀中右括号不超过左括号，等价于只保留搜索树中合法的分支。这与"从左到右扫描括号序列"的合法性判定完全一致。

目录

题意

思路

代码

复杂度

总结