go - 计算 Go 中唯一的括号组合总数

Question

比如输入是3，那么3对括号的可能组合，即:()()()，分别是()()(), ()(()), (())(), ((()))， 和 (()())。当输入为 3 时，总共有 5 种组合，因此您的程序应该返回 5。
我尝试使用这样的 Javascript:

function BracketCombinations(num) {

    function calculatePOssibilities (open, closed) {
        if (open === 0 && closed === 0)
            return 1;
        var res = 0;
        if (open > 0)
            res += calculatePOssibilities(open - 1, closed);
        if (closed > open)
            res += calculatePOssibilities(open, closed - 1);
        return res;
    }
    // code goes here  
    return calculatePOssibilities(num, num);
}

我知道，我可以将该代码转换为 Go，但如何使其更多 高效 ?

Answer 1

func BracketCombinations(n int64) int64 {
    var i big.Int
    i.Binomial(2*n, n)
    i.Div(&i, big.NewInt(n+1))
    return i.Int64()
}

我相信这会很有效，但为了进行适当的基准测试，我们需要建立一些测试参数。至少，它是一种非递归实现，因此它在大多数方面都应该胜过您的原始代码。

我是如何找到解决方案的:
我运行您的 javascript 代码以输出一系列数字。然后我在 Online Encyclopedia of Integer Sequences 中搜索了这一系列数字。 ，并找到了该系列的正式名称(加泰罗尼亚数字)，包括推导它的公式。然后我发现binomial(2n,n)/(n+1)公式应该最容易实现，因为 Go 标准库提供了一个二项式函数。