Search code examples
algorithmpuzzlecatalan

How to print all possible balanced parentheses for an expression?

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses):

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

The first example multiplies a*b, then multiplies that product by c, then multiplies that product by d. The second example first multiplies b*c, then multiplies that product by a, then multiplies that product by d.

Any valid parenthesized expression of 2n elements will necessarily have n ( and n ) with the property that, reading from left to right, there are always at least as many ( as ).

I know that for n numbers, the number of ways is the (n-1)th Catalan number. But how does one accurately generate all the resulting groupings?

Thanks

(As an aside: There are over 160 equivalent formulations of this problem, all based on different combinatorial objects enumerated by the Catalan Numbers. For the most up to date list of these, see Richard Stanley's Catalan Addendum.)

Solution

  • Use recursion

       for each balanced expression of n-1 parentheses 
     for each pos i from 0 to m of an expression
       add '('
       for each pos  j from i + 1 to m
          add ')' if expression is balanced

    The order you will get is the following:

    n=0: 

n=1: ()

n=2: []() , [()]

n=3: {}[]() , {[]}() , {[]()} , {}[()] , {[()]}

    Here I'm changing the parens each time (,[,{ to highlight how the algorithm works.