LeetCode59 - 括号生成 | 很多时候不懂事

📝 题目描述

题目链接：括号生成

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

示例：

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

💡 解题思路

方法一：回溯

这个思路很直观：

如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

也就是带有剪枝的深度优先搜索（DFS）/回溯。

方法二：动态规划与分治

任何一个合法的括号序列都可以拆分成这样一种结构：

"(" + 【合法的括号序列A】 + ")" + 【合法的括号序列B】

如果我们假设当前需要生成 $n$ 对括号，我们可以枚举内部包裹的序列 $A$ 有 $j$ 对括号，那么外部拼接的序列 $B$ 就有 $n−1−j$ 对括号（因为最外层的 () 已经占用了 $1$ 对）。

递推公式为：

$dp[i]="("+dp[j]+")"+dp[i−1−j] ，其中 j∈[0,i−1]。$

🔧 代码实现

1、回溯

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string current_str = "";
        // left 代表已放置的左括号数量，right 代表已放置的右括号数量
        backtrack(ans, current_str, 0, 0, n);
        return ans;
    }

private:
    void backtrack(vector<string>& ans, string& current_str, int left, int right, int n) {
        // 终止条件：字符串长度等于 2*n
        if (current_str.length() == 2 * n) {
            ans.push_back(current_str);
            return;
        }
        
        // 如果左括号没用完，可以加左括号
        if (left < n) {
            current_str.push_back('(');
            backtrack(ans, current_str, left + 1, right, n);
            current_str.pop_back(); // 回溯状态
        }
        
        // 如果右括号数量小于左括号，说明可以加右括号来闭合
        if (right < left) {
            current_str.push_back(')');
            backtrack(ans, current_str, left, right + 1, n);
            current_str.pop_back(); // 回溯状态
        }
    }
};

2、动态规划与分治

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) return {""};
        
        // dp[i] 表示使用 i 对括号能够生成的所有合法组合
        vector<vector<string>> dp(n + 1);
        dp[0] = {""};    // 0对括号就是空串
        dp[1] = {"()"};  // 1对括号
        
        for (int i = 2; i <= n; i++) {
            // 枚举括号内包含的括号对数 j
            for (int j = 0; j < i; j++) {
                // p 代表内部的组合 A，q 代表外部的组合 B
                for (string p : dp[j]) {
                    for (string q : dp[i - 1 - j]) {
                        dp[i].push_back("(" + p + ")" + q);
                    }
                }
            }
        }
        return dp[n];
    }
};

📊 复杂度分析

1、回溯

时间复杂度： $O(\frac{4^n}{\sqrt{n}})$ ，这个复杂度对应的是第 n 个卡特兰数（Catalan number）。因为生成的有效组合数量是由卡特兰数决定的，而我们只生成有效组合，没有做多余的无效搜索。
空间复杂度： $O(n)$ ，除了存储答案的数组外，递归调用栈的深度最深为 2n，另外字符串 s 的长度最大也是 2n。

2、动态规划与分治

时间复杂度： $O(\frac{4^n}{\sqrt{n}})$ ，同样受到卡特兰数的限制。
空间复杂度： $O(\frac{4^n}{\sqrt{n}})$ ，由于要保存中间的所有状态字典 $dp[0...n]$ ，空间开销会比回溯法大。

🎯 总结

核心思想：两种方法都要掌握。