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)==')')// if closing braces are more, it can never be balanced, and there we need a global variable
{
count2++;
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 the below condition for k is not taken, we will get duplicates for every pair
if(i<n)
{
*(a+i)=ch;
catalan(a,n,(i+1),'(');
catalan(a,n,(i+1),')');
}
k++;
// 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;
