力扣-22. 生成括号（Generate Parentheses）

最后编辑于2025-07-13

22. 生成括号（Generate Parentheses）

Medium

给定 n 对括号，写一个函数生成所有由 n 对括号组成的合法（well-formed） 括号字符串。

示例 1：

输入： n = 3
输出： [("((()))","(()())","(())()","()(())","()()()")]

示例 2：

输入： n = 1
输出： [("()")]

约束：

  • 1 <= n <= 8

解题思路（回溯 / 递归）

这类“列出所有组合”的题型常用 回溯（Backtracking）。对于生成合法括号，关键在于维护左右括号剩余数量，并保证任何时刻已生成的前缀都是合法的（即左括号剩余数不能大于右括号剩余数，否则会出现以 ) 开头或中途负平衡的情形）。

定义递归函数 dfs(left, right, cur)：

  • left：当前还能放的左括号数量（’(‘）。
  • right：当前还能放的右括号数量（’)’）。
  • cur：当前构造的字符串。

递归规则：

  1. 若 left > right，说明前缀不合法（右括号比左括号先用完），直接返回。
  2. 若 left == 0 && right == 0，则 cur 为一个完整合法解，加入结果集。
  3. 若 left > 0，可以放一个左括号：dfs(left-1, right, cur+'(')。
  4. 若 right > 0，可以放一个右括号：dfs(left, right-1, cur+')')。

该方法复杂度与卡塔兰数相关，生成结果数为第 n 个卡塔兰数，符合题目规模限制（n <= 8）。

方法一：标准回溯（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(n, n, "", res);
        return res;
    }
    void dfs(int left, int right, string cur, vector<string> &res) {
        if (left > right) return; // 不合法的前缀
        if (left == 0 && right == 0) res.push_back(cur);
        else {
            if (left > 0) dfs(left - 1, right, cur + '(', res);
            if (right > 0) dfs(left, right - 1, cur + ')', res);
        }
    }
};

方法二：基于已有解的插入法（使用集合去重）

  • 思路来自于构造法：由 n-1 的所有合法解，在每个字符串的任意一个左括号后插入一对 ()，或在开头插入 ()，然后用集合去重得到 n 的所有解。
  • 该方法可用作思路拓展，但需要集合去重来避免重复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        unordered_set<string> st;
        if (n == 0) st.insert("");
        else {
            vector<string> pre = generateParenthesis(n - 1);
            for (auto a : pre) {
                for (int i = 0; i < a.size(); ++i) {
                    if (a[i] == '(') {
                        a.insert(a.begin() + i + 1, '(');
                        a.insert(a.begin() + i + 2, ')');
                        st.insert(a);
                        a.erase(a.begin() + i + 1, a.begin() + i + 3);
                    }
                }
                st.insert("()" + a);
            }
        }
        return vector<string>(st.begin(), st.end());
    }
};

作者想说的话：
生成括号是回溯的典型题，关键在于维护可用左右括号数量并及时剪枝（left > right 时剪掉不合法前缀）。回溯方法直观、效率高且易于理解；插入法是有趣的构造思路，但需要额外去重。