LC22：括号生成

题目描述

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

示例1：

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

示例2：

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

提示：

• 1 <= n <= 8

分析

本题使用动态规划的思想，使用一个 dp 数组保存括号对数为 n - 1 时的括号组合，进而推导出括号对数为 n 时的括号组合。难点在于如何建立从 n - 1 到 n 的转换方程。

括号对数从 n - 1 增加到 n 时增加了一个括号，由于一定有一个括号的左括号在最左边，我们可以认为这个括号就是新加入的括号。我们再将剩下的 n - 1 个括号拆成 在新括号里 和 在新括号外 两组，这样新的括号组合就变成了：

( dp[k] ) dp[n - 1 - k]

dp[k] 表示当 n = k 时所有可能的括号组合，其中 k 的变化范围为从 0 到 n-1。

我们只需要遍历括号组合建立 dp 数组即可得到答案。

对于该方法正确性的证明：
为了证明该动态规划方法不会生成重复的有效括号组合，我们需要证明每个有效组合可以被唯一地分解为形式 (A)B，其中 A 是 k 对有效组合，B 是 n - 1 - k 对有效组合，且这种分解方式唯一。
证明步骤：
​唯一分解性：
任意有效括号组合的第一个字符必为左括号 (。
设该左括号对应的右括号位置为 i，则组合可表示为 (A)B，其中 A 是 [1, i - 1] 的子串，B 是 [i + 1, 2n - 1] 的子串。
A 和 B 本身必须是有效组合，且 A 包含 k 对括号，B 包含 n - 1 - k 对括号（k 从 0 到 n - 1）。
由于括号的严格匹配规则，每个组合的分解方式唯一，即 k 唯一确定。
​动态规划的构造过程：
在动态规划中，我们遍历所有可能的 k（0 ≤ k ≤ n - 1），并将 dp[k] 和 dp[n - 1 - k] 组合为 (A)B。
由于每个组合仅对应一个 k，且在遍历 k 时，所有可能的 A 和 B 的组合都被覆盖，因此每个有效组合会被生成且仅生成一次。
​归纳法验证：
​基础情况：当 n = 1，唯一组合为 ()，无重复。
​归纳假设：假设对于 m < n，dp[m] 包含所有有效组合且无重复。
​归纳步骤：对于 dp[n]，其每个元素形如 (A)B，其中 A ∈ dp[k]，B ∈ dp[n - 1 - k]。由于 k 唯一，且 A 和 B 无重复（归纳假设），因此 (A)B 的组合也不重复。

时间复杂度为 $O(\frac{4^n}{\sqrt n})$.

实现

class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            dp.add(new ArrayList<>());
        }
        dp.get(0).add(""); // 0 个括号对时 dp 为空字符串
        // ( dp[k] ) dp[n - 1 - k]
        // 每个循环建立当 n = i 时的 dp 数组
        for (int  i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                List<String> lst1 = dp.get(j);    // dp[k]
                List<String> lst2 = dp.get(i - j);  // dp[n - 1 - k]
                for (String s1: lst1) {
                    StringBuilder sb = new StringBuilder(); // 使用 StringBuilder 效率比直接拼接字符串更高
                    sb.append("(").append(s1).append(")");
                    for (String s2: lst2) {
                        StringBuilder sb2 = new StringBuilder(sb).append(s2);
                        dp.get(i + 1).add(sb2.toString());
                    }
                }
            }
        }
        return dp.get(n);
    }
}