Bracket Combination

29 Nov 2011

This is a problem posed by my girlfriend's boss at NovaLeaf.

The problem is:

Given n brackets, how many are the combination of valid brackets? For example, 2 brackets have [][] and [[]].

It's obvious that we can go after a brute-force method that looks like this:

def count(k, m) # k = number of opens, m = number of unuseds return 1 if k == 0 and m == 0 r = 0 r = r + count(k-1, m) if k > 0 # add closed bracket r = r + count(k+1, m-1) if m > 0 # add opened bracket return r end puts count(0, n) # result of n brackets

However, that kind of solution will never ever work at the level of TopCoder.com or Google CodeJam.

Of course, we need a dynamic-programming approach to count it efficiently.

Let say a[0] a[1] a[2] … a[2n] is the valid positioning of n brackets.

The critical point for a dynamic-programming approach is to see that you do not need all the information to solve the problem.

For example, I finish a[i], use m brackets, and have k opened brackets. What I need to know to count is how many of a[i+1]…a[2n], use n-m brackets, and have k closed brackets are there.

And that's it.

Let's formulate the dynamic-programming approach to this problem:

Let a[0] a[1] ... a[2n] be the sequence of ( and ) d[i, k, m] is the number of combinations that have k opened brackets and use m brackets. The answer is d[2n, 0, n] The base case is d[1, 1, 1] = 1 The general case is d[i, k, m] = 0 d[i, k, m] += d[i-1, k+1, m] d[i, k, m] += d[i-1, k-1, m-1]

The explanation is:

At (i, k, m), it can come from closing one more brackets, which is from (i-1, k+1, m). Or, it can come from opening one more brackets, which is from (i-1, k-1, m-1).

Give it a kudos