Problem Statement: Given n pair of parentheses find how many different valid combination of parentheses are possible.
Solution: In order to under solution to this problem lets take an example. Assume that we are given three pairs of parentheses. A valid permutation of these parentheses will always have left number of left parentheses more than or equal to number of right p arentheses. Lets see an example
Let the pair [l,r] represent number of left parentheses and number of right parentheses encountered in the permutation so far.
a. Valid Parentheses ,
( [1,0] ( [2,0] ) [2,1] ) [2,2] ( [3,2] ) [3,3]
b. Invalid Parentheses
([1,0] )[1,1] )[1,2 invalid ] ( ( )
Above examples demonstrate that for a permutation to be valid number of left parentheses in the permutation at any position should be more than or equal to number right parentheses
Now lets try to find out all possible permutation for 3 pairs of parentheses. It can be noted that all permutations will have six characters , and any character can be either ‘(‘ left parentheses or ‘)’ right parentheses as long as it does not violate above property, let us represent left parentheses ‘(‘ by 0 and right parentheses ‘)’ by 1. So that a string of zeros and ones represent a permutation of parentheses
As you can see in the above tree that the tree is binary and that tree stops branching as long as number of left parentheses becomes 3 which is equal to the number of pairs of parenthesis. Thus number of valid parentheses is equal to number of node which have l ( number of left parentheses) equal to n (number of pairs of parentheses). and for all other cases we have two choices we increment l and if r < l we can increment r also where r is number of right parentheses. The presented algorithm does exactly that