Tuesday, June 23, 2015

Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?

For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()

We have a simple solution to this problem by using recursion. We design this method as follows.

It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.

As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.

Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.

When we don't have any left or right braces remaining, we can print the contents of the buffer.

Here is the Java implementation.