# 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). ```