Another interesting puzzle:

## Parenthesis Permutation

Given N pair of parenthesis. Write an algorithm which would print out all permutations, possible with
those parenthesis given that parenthesis are in correct order (i.e. every open parenthesis is matched
with closed parenthesis) For .e.g. .. N =3 should give:

()()()

(()())

()(())

(())()

((()))

There are recursive solutions for this you can find just by googling. I thought of a non-recursive solution

Click to view my solution

The basic idea is to construct a Binary Tree, where left node is *'***('** extra and right node is *'***)'** extra from the current node. Each node has a **weight = number of '(' - number of ')'. **

We start with a root node **'('** at level **0 **and create the tree such that the **2N-1** level will contain permutations for **N** pairs.

Now when constructing the tree, we create a child only if:

- Weight of incoming child is not less than 0

- When weight >= 0, it should be less than or equal to the numbers of levels to create, so that we have enough parenthesis left to balance the string

Let's take a look at the tree created (string -> weight) for **N = 3**:

An optimization - the last level is not required since all that is added is a '

*)'*Now the code. Infact not using a tree at all, just a linked list and traversing in preorder style, using the concepts above of adding a child. I could have used an array instead of linked list, but it suffers from list expansion frequently hence slowing everything down.

The code to generate the tree picture is

here
Infact the number of permutations for a given N pair form a series called Catalan Numbers . It goes like this:

N=1 P=1
N=2 P=2
N=3 P=5
N=4 P=14
N=5 P=42
N=6 P=132
N=7 P=429
N=8 P=1430
N=9 P=4862
N=10 P=16796
N=11 P=58786
N=12 P=208012
N=13 P=742900
N=14 P=2674440
N=15 P=9694845