22 括号生成

一、题目

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

二、题解

方法一：回溯法

思路：使用 回溯 / DFS。

1. 核心思路

括号是否合法，关键在于生成过程中不能出现右括号比左括号多的情况。

对于 n 对括号：

  • 左括号最多只能使用 n 个；
  • 右括号最多只能使用 n 个；
  • 在任意时刻，右括号数量不能超过左括号数量。

核心思想是：

  • 每次尝试添加一个左括号或右括号；
  • 如果左括号数量还没有达到 n，就可以添加左括号；
  • 如果右括号数量小于左括号数量，才可以添加右括号。

2. 具体步骤

  1. 使用一个 StringBuilder 记录当前正在生成的括号字符串。
  2. 使用 left 记录已经使用的左括号数量。
  3. 使用 right 记录已经使用的右括号数量。
  4. 如果当前字符串长度等于 2 * n，说明生成了一个完整合法结果，加入答案。
  5. 如果 left < n，可以添加左括号。
  6. 如果 right < left，可以添加右括号。
  7. 每次递归结束后，需要撤销刚才添加的括号，这就是回溯。

3. 关键逻辑

if (left < n) {
    path.append('(');
    backtrack(result, path, left + 1, right, n);
    path.deleteCharAt(path.length() - 1);
}

if (right < left) {
    path.append(')');
    backtrack(result, path, left, right + 1, n);
    path.deleteCharAt(path.length() - 1);
}

解释：

  • 如果 left < n，说明左括号还没有用完，可以继续添加左括号；
  • 如果 right < left，说明当前有左括号可以匹配，所以可以添加右括号；
  • 每次递归后删除最后一个字符，是为了回到上一步，继续尝试其他情况。

4. 代码

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        // 1. 定义结果集合
        List<String> result = new ArrayList<>();

        // 2. 从空字符串开始回溯
        backtrack(result, new StringBuilder(), 0, 0, n);

        // 3. 返回结果
        return result;
    }

    /**
     * @param result 保存所有合法结果
     * @param path 当前正在生成的括号字符串
     * @param left 已经使用的左括号数量
     * @param right 已经使用的右括号数量
     * @param n 需要生成的括号对数
     */
    private void backtrack(List<String> result, StringBuilder path, int left, int right, int n) {
        // 当字符串长度达到 2 * n，说明已经生成一个完整结果
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }

        // 情况一：左括号还没有用完，可以添加左括号
        if (left < n) {
            path.append('(');

            backtrack(result, path, left + 1, right, n);

            // 回溯：撤销刚才添加的左括号
            path.deleteCharAt(path.length() - 1);
        }

        // 情况二：右括号数量小于左括号数量时，才可以添加右括号
        if (right < left) {
            path.append(')');

            backtrack(result, path, left, right + 1, n);

            // 回溯：撤销刚才添加的右括号
            path.deleteCharAt(path.length() - 1);
        }
    }
}

5. 复杂度分析

时间复杂度：O(Cn×n)O(C_n \times n)

说明：合法括号组合的数量是第 n 个卡特兰数 C_n，每个结果长度为 2n，所以时间复杂度可以记为 O(Cn×n)O(C_n \times n)。

空间复杂度：O(n)O(n)

说明：递归深度最多是 2n，忽略结果数组所占空间，空间复杂度是 O(n)O(n)。

方法二：动态规划

思路：使用 动态规划 / 递推。

1. 核心思路

方法一是通过回溯逐个生成结果。

方法二可以从较小规模的合法括号组合推出较大规模的合法括号组合。

对于 n 对括号，任意一个合法组合都可以拆成：

( A ) B

其中：

  • A 是若干对括号组成的合法组合；
  • B 也是若干对括号组成的合法组合；
  • 如果 A 中有 j 对括号，那么 B 中就有 n - 1 - j 对括号。

所以可以枚举：

dp[n] = "(" + dp[j] + ")" + dp[n - 1 - j]

这种方法的核心是：

  • 先求出较小括号对数的所有合法结果；
  • 再通过组合的方式生成更大括号对数的结果；
  • 最后得到 dp[n]。

2. 具体步骤

  1. 定义 dp[i] 表示 i 对括号能够生成的所有合法组合。
  2. 初始化 dp[0] = [""]，表示 0 对括号时只有空字符串。
  3. 从 i = 1 开始递推到 n。
  4. 对于每个 i，枚举左边括号内部有多少对括号。
  5. 如果括号内部有 j 对，那么括号外部右边有 i - 1 - j 对。
  6. 将结果拼接成 "(" + left + ")" + right。
  7. 最终返回 dp[n]。

3. 关键逻辑

for (int j = 0; j < i; j++) {
    for (String left : dp[j]) {
        for (String right : dp[i - 1 - j]) {
            dp[i].add("(" + left + ")" + right);
        }
    }
}

解释：

  • j 表示当前最外层括号里面有多少对括号；
  • i - 1 - j 表示最外层括号右边还有多少对括号；
  • 通过 "(" + left + ")" + right 可以组合出所有合法情况。

4. 代码

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        // 1. 定义 dp 数组
        // dp[i] 表示 i 对括号能生成的所有合法组合
        List<String>[] dp = new ArrayList[n + 1];

        // 2. 初始化每一个位置
        for (int i = 0; i <= n; i++) {
            dp[i] = new ArrayList<>();
        }

        // 3. 初始化 dp[0]
        // 0 对括号只有一种情况：空字符串
        dp[0].add("");

        // 4. 开始递推
        for (int i = 1; i <= n; i++) {
            // j 表示最外层括号里面有多少对括号
            for (int j = 0; j < i; j++) {
                // left 是最外层括号里面的合法组合
                for (String left : dp[j]) {
                    // right 是最外层括号右边的合法组合
                    for (String right : dp[i - 1 - j]) {
                        dp[i].add("(" + left + ")" + right);
                    }
                }
            }
        }

        // 5. 返回 n 对括号的所有合法组合
        return dp[n];
    }
}

5. 复杂度分析

时间复杂度：O(Cn×n)O(C_n \times n)

说明：最终需要生成所有合法括号组合，合法组合数量是卡特兰数 C_n，每个字符串长度为 2n，所以时间复杂度为 O(Cn×n)O(C_n \times n)。

空间复杂度：O(Cn×n)O(C_n \times n)

说明：动态规划数组中保存了从 0 到 n 对括号的所有合法组合，因此空间复杂度为 O(Cn×n)O(C_n \times n)。

评论