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);
printf("how many pair of parentheses do you want : ");
catalan(a,n,0,'('); // calling the Catalan function
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
return 1 + balanced(a,n,++i,count1,count2);else
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)}
if(result==0 && flag==0)