Count total unique parenthesis combinations in Go

user_15579494 0
Viewed 79

For example, if the input is 3, then the possible combinations of 3 pairs of parenthesis, namely: ()()(), are ()()(), ()(()), (())(), ((())), and (()()). There are 5 total combinations when the input is 3, so your program should return 5. I try using Javascript like this :

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);
}

I know, i can just transform that code to Go, but how to make it more efficient?

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

I believe this will be efficient, but in order to do a proper benchmark we would need to establish some testing parameters. At the very least, it is a non-recursive implementation, so it should beat your original code in most regards.

How I found the solution:

I ran your javascript code to output a series of numbers. I then searched that series of numbers in the Online Encyclopedia of Integer Sequences, and found a formal name for the series (Catalan numbers), including formulae to derive it. I then found that the binomial(2n,n)/(n+1) formula should be easiest to implement, as the Go standard library supplies a binomial function.

user_114246730
Related