22.括号生成：暴力枚举 / 回溯

【LetMeFly】22.括号生成：暴力枚举 / 回溯

力扣题目链接：https://leetcode.cn/problems/generate-parentheses/

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 1 <= n <= 8

解题方法一：暴力枚举（二进制状态压缩）

$n$对括号组成的字符串长度$2n$，我们枚举长度为$2n$的字符串所有的$2^{2n}$种左右括号的可能，如果是合法括号序列则加入答案中。

  • 时间复杂度$O(4^{n}\times n)$。共有$2^{2n}$种可能，每种可能需要$O(n)$的时间去判断是否合法。不过实际上会有很多状态提前退出枚举。
  • 空间复杂度$O(n)$，空间复杂度来自临时构造的字符串，力扣返回值不计入算法空间复杂度。

AC代码

C++

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
/*
 * @LastEditTime: 2026-10-02 16:43:41
 */
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        n *= 2;
        for (int i = 0, to = 1 << n; i < to; i++) {
            string s(n, '0');
            bool ok = true;
            int cnt_left = 0;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    cnt_left++;
                    s[j] = '(';
                } else if (!cnt_left) {
                    ok = false;
                    break;
                } else {
                    cnt_left--;
                    s[j] = ')';
                }
            }
            if (cnt_left) {
                continue;
            }
            if (ok) {
                ans.push_back(s);
            }
        }
        return ans;
    }
};

解题方法二：回溯

写一个函数dfs尝试字符串当前位置的每一种可能。dfs接收参数：s, idx, diff, left, right表示字符串当前应该填充s[idx]位置，还有left个左括号和right个右括号，当前左括号比右括号多diff个。

  • 如果left和right都为0，说明已经填充完毕，加入答案中。
  • 如果left非零，可尝试填充左括号。
  • 如果diff非零且right非零，可尝试填充右括号。

以上。

  • 时间复杂度$O(4^{n})$。实际上只会枚举所有合法括号序列。
  • 空间复杂度$O(n)$，临时构造的字符串、最大递归深度的空间复杂度都是$O(n)$，力扣返回值不计入算法空间复杂度。

AC代码

C++

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
/*
 * @LastEditTime: 2026-10-02 16:54:44
 */
class Solution {
private:
    vector<string> ans;

    void dfs(string& s, int idx, int diff, int left, int right) {
        if (!left && !right) {
            ans.push_back(s);
        }
        if (left) {
            s[idx] = '(';
            dfs(s, idx + 1, diff + 1, left - 1, right);
        }
        if (diff && right) {
            s[idx] = ')';
            dfs(s, idx + 1, diff - 1, left, right - 1);
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        string s(n * 2, ' ');
        dfs(s, 0, 0, n, n);
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源