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!!


                                           

#include<stdio.h>
#include<string.h>
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;
scanf("%d",&n);
n=n*2;

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 ')'
   
      if(i<n)
      { 
          if(*(a+i)=='(')
          {
               count1++;
               return  -1 + balanced(a,n,++i,count1,count2);
          }

else if(*(a+i)==')')
{
count2++;

               // 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);
}}

       else
           return 0;
}


void catalan(char *a, int n, int i, char ch)
{

static int k=0;             // needed it, see below
if(i<n)
{
*(a+i)=ch;
catalan(a,n,(i+1),'(');
catalan(a,n,(i+1),')');
}
k++;

           // 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)      
{
flag=0;
int result=balanced(a,n,0,0,0);

if(result==0 && flag==0)
{
int j=0;
while(j<n)
{ printf("%c",*(a+j));
j++;
}
printf("\n");
}
}
return;

 }