Go语言如何高效计算合法括号组合的总数量

你当前实现的递归方案属于无缓存的暴力递归，存在大量重复的子状态计算，时间复杂度为指数级，n稍大时运行效率会非常低。可以通过以下三种方案优化，效率从低到高排列：

1. 记忆化搜索（最小改动优化） #

逻辑和你原有的递归完全一致，仅新增缓存存储已经计算过的「剩余可用左括号数open、剩余可用右括号数closed」对应的结果，避免重复计算。优化后时间复杂度为O(n²)，空间复杂度O(n²)。
Go语言示例代码：

func BracketCombinations(num int) int {
    // 缓存二维数组，memo[open][closed]存储对应状态的结果
    memo := make([][]int, num+1)
    for i := range memo {
        memo[i] = make([]int, num+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    var dfs func(int, int) int
    dfs = func(open, closed int) int {
        if open == 0 && closed == 0 {
            return 1
        }
        if memo[open][closed] != -1 {
            return memo[open][closed]
        }
        res := 0
        if open > 0 {
            res += dfs(open-1, closed)
        }
        if closed > open {
            res += dfs(open, closed-1)
        }
        memo[open][closed] = res
        return res
    }
    return dfs(num, num)
}

2. 动态规划递推 #

利用卡特兰数的动态规划递推规则计算：dp[i]表示i对括号的合法组合数，初始状态dp[0] = 1，递推公式为dp[i] = sum(dp[j] * dp[i-j-1])（j从0遍历到i-1）。优化后时间复杂度O(n²)，空间复杂度O(n)。
Go语言示例代码：

func BracketCombinations(num int) int {
    dp := make([]int, num+1)
    dp[0] = 1
    for i := 1; i <= num; i++ {
        for j := 0; j < i; j++ {
            dp[i] += dp[j] * dp[i-j-1]
        }
    }
    return dp[num]
}

3. 卡特兰数公式直接计算（最高效方案） #

n对合法括号的组合数本质就是第n个卡特兰数，可以直接用组合数公式计算：C(n) = (2n)!/(n! * (n+1)!)，计算时可以分步乘除避免中间结果溢出，时间复杂度O(n)，空间复杂度O(1)，是三种方案里效率最高的，适合n较大的场景。
Go语言示例代码：

func BracketCombinations(num int) int {
    res := 1
    for i := 1; i <= num; i++ {
        res = res * (num + i) / i
    }
    res = res / (num + 1)
    return res
}

如果num过大，结果会超出int的存储范围，可以根据需求替换为int64或者大整数类型。

内容的提问来源于stack exchange，提问作者Muslihudin