## Valid Parentheses Combinations

*Problem Statement:* You are given a number of pairs of parentheses. You are supposed to print all valid combinations using all these parentheses.

This question is only an example of questions where you are supposed to find all the permutations of a set of elements. I am using this question to demonstrate the method to perform all such permutations.

So how do you go about finding all permutations. Here is a great method to do so. Start with a single parentheses. Now start inserting the remaining parentheses at all the possible locations. Here is how it goes if we are given 2 pairs of parentheses.

(,),(,) //available elements

Now constructing all possibilites:

(//start —0

()//inserting ) to the right in 0 —1

)(//inserting ) to the left in 0 —2

()(//inserting ( to the right in 1 or left of 2 —3

(()//inserting ( either in the middle or left of 1 —4

)((//inserting ( in the middle of 2 —5

()(), ())( , )()(//inserting ) at different places in 3 —6

(()) , ()() , )(()//inserting ) at different places in 4 —7

)(() , )()( , ))((//inserting ) at different places in 5 —8

Now all you need to do is find the valid combinations from those generated in 6, 7 and 8. Handy technique, right?! 🙂

* PS:* Leave a comment if you don’t know how to check validity of parentheses combinations and I’ll write a post on that as well.

Being a “compiler guy”, I’d take a different approach.

First observe is that the list of perfectly balanced paren-expressions

is completely described by the context-free grammar:

B = E | B ‘(‘ B ‘)’ /* E is the empty string. */

This gives a nice recursive relation: for generating all the

paren-expressions of length N, first generate all the

paren-expressions of length X and Y, such that X + Y == (N – 2).

So, for N = 6, you generate the following sets:

X = 0 (only the empty string), Y = 4 (some set of strings) — (A)

X = 2 (paren-expressions always have an even length), Y = 2 — (B)

X = 4, Y = 0 — (C)

Then iterate through this set S = { A, B, C }. Each element of this set

S is itself a pair of set of strings. For each pair we generate all

the strings possible by taking `x` from the first set in the pair and

`y` from the second, and adding `x` + “(” + `y` + “)” to our solution

set (the one we’re trying to calculate). This should result in the

solution set containing exactly all the paren-expressions of length N.

This is one of those algorithms which are harder to write down than to

intuitively understand. 🙂

For completeness, here is a (very slow) implementation in Haskell:

b n = if n == 0 then [“”] — One empty string

else

let limit = n / 2

stringList = [(b $ 2 * x, b $ 2 * y)

| x <- [0..limit – 1],

y [m ++ “(” ++ n ++ “)” |

m <- x, n <- y]) stringList

PS: Awesome work regularly updating the blog. Most people lose motivation. 🙂

Hah! Never thought of it that way. Nice 🙂 But won’t that be slower? Just wondering.

And thanks, plan to continue with the regular updates. 🙂

Of course, since you’re given “The number of parens is X”, you’ll have the feed “The length of the paren-expr is 2 * X” to the above algorithm.

Yes. That is pretty obvious 🙂