LeetCode 22 - 括号生成（Generate Parentheses）

问题描述

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

示例：

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

解题思路

这道题目要求我们生成所有可能的有效括号组合，是一个典型的回溯（深度优先搜索）问题。我们也可以用动态规划的方式解决。下面我将详细介绍这两种方法。

方法一：回溯算法（DFS）

回溯算法的核心思想是通过递归的方式，逐步构建解决方案，并在不满足条件的情况下进行回溯。

对于括号生成问题，我们可以通过以下思路解决：

维护两个变量 left 和 right，分别表示已经放置的左括号和右括号的数量
对于每个位置，我们有两种选择：放置左括号或放置右括号
放置左括号的条件：当前已放置的左括号数量小于 n
放置右括号的条件：当前已放置的右括号数量小于左括号数量
当左括号和右括号的数量都等于 n 时，我们得到一个有效的括号组合

这样，我们可以通过 DFS 遍历所有可能的组合，并只保留有效的组合。

让我们用一个简单的例子（n=2）来说明这个过程：

初始状态：""，left=0，right=0
    选择左括号："("，left=1，right=0
        选择左括号："(("，left=2，right=0
            选择右括号："(()"，left=2，right=1
                选择右括号："(())"，left=2，right=2，得到一个有效组合
        选择右括号："()"，left=1，right=1
            选择左括号："()("，left=2，right=1
                选择右括号："()()"，left=2，right=2，得到一个有效组合

方法二：动态规划

动态规划的思路是基于已知的结果推导出未知的结果。对于括号生成问题，我们可以这样思考：

设 dp[i] 表示 i 对括号的所有有效组合，那么对于 dp[n]，我们可以枚举左括号的位置，然后将问题分解为已知的子问题。

具体来说，我们可以通过以下公式来生成 dp[n]：

$$
dp[n] = \sum_{i=0}^{n-1} (dp[i]) + dp[n-1-i]
$$

其中 i 表示左括号内部包含的括号对数，n-1-i 表示右括号后面的括号对数。

实现细节

方法一：回溯算法（DFS）实现

func generateParenthesis(n int) []string {
    result := []string{}
    // 创建一个临时数组来存储当前构建的括号字符串
    tmpArray := make([]byte, 2*n)
  
    // 定义 DFS 函数
    var dfs func(index, left, right int)
    dfs = func(index, left, right int) {
        // 当我们放满了所有括号时，添加到结果集
        if index == 2*n {
            result = append(result, string(tmpArray))
            return
        }
      
        // 如果左括号数量小于 n，可以放置左括号
        if left < n {
            tmpArray[index] = '('
            dfs(index+1, left+1, right)
        }
      
        // 如果右括号数量小于左括号数量，可以放置右括号
        if right < left {
            tmpArray[index] = ')'
            dfs(index+1, left, right+1)
        }
    }
  
    // 从第一个位置、零个左右括号开始 DFS
    dfs(0, 0, 0)
  
    return result
}

方法二：动态规划实现

func generateParenthesis(n int) []string {
    if n == 0 {
        return []string{""}
    }
  
    // dp[i] 表示 i 对括号的所有有效组合
    dp := make([][]string, n+1)
    dp[0] = []string{""}
  
    for i := 1; i <= n; i++ {
        dp[i] = []string{}
        for j := 0; j < i; j++ {
            // 枚举左括号内部的括号对数 j
            for _, left := range dp[j] {
                for _, right := range dp[i-1-j] {
                    // 将 "(" + dp[j] + ")" + dp[i-1-j] 添加到 dp[i]
                    dp[i] = append(dp[i], "(" + left + ")" + right)
                }
            }
        }
    }
  
    return dp[n]
}

执行示例

让我们以 n=3 为例，追踪方法一（回溯算法）的执行过程：

初始状态：tmpArray = [_, _, _, _, _, _], index=0, left=0, right=0
放置左括号：tmpArray = [(, _, _, _, _, _], index=1, left=1, right=0
继续放置左括号：tmpArray = [(, (, _, _, _, _], index=2, left=2, right=0
继续放置左括号：tmpArray = [(, (, (, _, _, _], index=3, left=3, right=0
放置右括号：tmpArray = [(, (, (, ), _, _], index=4, left=3, right=1
继续放置右括号：tmpArray = [(, (, (, ), ), _], index=5, left=3, right=2
继续放置右括号：tmpArray = [(, (, (, ), ), )], index=6, left=3, right=3，添加到结果集：“((()))”
回溯到步骤 5，尝试放置另一个右括号…

通过深度优先遍历所有可能的情况，我们最终得到所有有效的括号组合。

方法比较

方面	回溯算法（DFS）	动态规划
时间复杂度	$O(\frac{4^n}{\sqrt(n)})$	$O(\frac{4^n}{n^{3/2}})$
空间复杂度	O(n)	$O(\frac{4^n}{n^{3/2}})$
优点	直观，易于理解	避免重复计算
缺点	可能有重复计算	需要额外的存储空间
推荐度	★★★★★	★★★☆☆

复杂度分析

回溯算法（DFS）

时间复杂度：$O(\frac{4^n}{\sqrt{n}})$，这是第 n 个卡特兰数的近似值，表示长度为 2n 的合法括号序列的数量。
空间复杂度：$O(n)$，递归的深度最多为 2n，而我们需要一个长度为 2n 的数组来存储当前构建的括号字符串。

动态规划

时间复杂度：$O(\frac{4^n}{n^{3/2}})$，同样是卡特兰数的近似值。
空间复杂度：$O(\frac{4^n}{n^{3/2}})$，需要存储所有中间结果。

关键收获

回溯算法是解决生成所有可能组合问题的有力工具，特别适合有明确约束条件的问题。
在处理括号问题时，我们需要记住一个核心规则：右括号数量不能超过左括号数量。
动态规划可以通过分解问题并复用子问题的解来解决复杂问题。
这个问题是卡特兰数在计算机科学中的一个应用实例，卡特兰数描述了许多组合问题中的计数。