Tuesday, November 25, 2014

Code to generate all possible combinations of balanced parentheses (equal to Catalan number) using recursion

Earlier, I thought that Catalan numbers were limited to my CS lab assignment only, but when I searched for it and looked for further details of it on wiki, I was fascinated by its applications in mathematics. I would write about it later when I understand those concepts to make it clear for others.

But right now, I am writing this post because I got an assignment in my DS lab and they wanted me to do this : given a number n,  print all the possible combinations of balanced parentheses, the total number of which would be ( for now, let us assume mysteriously ) equal to  the Catalan number, and yeah that too using recursion.

Here, n represents pairs of parentheses.
For example, n=1  =>  ()
                       n=2  =>  () ()

I hope this makes the question a bit clear before going for the code part.

I searched for the program on the net after spending a few hours on it, but to no rescue. Every single code here was using an explicit stack. So, I decided that I would post once I code it, and see here I am. I would like to explain the code, and would surely do it someday. But, for now I am just pasting the code so that, if in any confusion or problem, you can have a look at it, and if someone is truly interested, can also understand it. I would update it with the explanation part in the near future. Till then, have fun time breaking the code and building your own!!


int flag=0;    // I needed this, you will understand this if you go through the program

int balanced(char *a, int n, int i, int count1, int count2);
void catalan(char *a, int n, int i, char ch);

int main()
printf("how many pair of parentheses do you want : ");
int n;

char a[n];

catalan(a,n,0,'(');       // calling the Catalan function
return 0;

int balanced(char *a, int n, int i, int count1, int count2)
       // in this function, I am checking whether the generated pair is balanced or not
      //i assigned -1 to '(' and +1 to ')'
               return  -1 + balanced(a,n,++i,count1,count2);
else if(*(a+i)==')')
               // if closing braces are more, it can never be balanced, and there we need a global variable
if(count2>count1)   flag=1;
   return 1 + balanced(a,n,++i,count1,count2);
           return 0;

void catalan(char *a, int n, int i, char ch)
static int k=0;             // needed it, see below
           // if the below condition for k is not taken, we will get duplicates for every pair
           // reason -> have a look at the recursive conditions, the answer lies there
if(i==n && k%2!=0)      
int result=balanced(a,n,0,0,0);

if(result==0 && flag==0)
int j=0;
{ printf("%c",*(a+j));


  1. This comment has been removed by the author.

  2. This comment has been removed by the author.

  3. For some reason C++ code being posted is not displayed correctly here and is rather truncated.

    1. Here's what I was trying to post: http://ideone.com/llyFHn
      I think its much more intuitive than the current solution.