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