Thursday, August 10, 2006

How many possible Brackets?

/******
Given a number n, print all possible combinations of n pairs of braces that are balanced
I/P:1
O/P:
()

I/P:2
(())
()()

I/P:3
O/P:
((()))
(()())
(())()
()(())
()()()

I/P:4
O/P:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

******/
int lbCount;
int rbCount;
void printLeftBrace(int index);
void printRightBrace(int index);
void printLeftBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
lbCount--;
temp[index] = ')';
if( lbCount == 0 && rbCount == 0)
{
printf("%s\n",temp);
return;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;

}
}
else
{
if(rbCount lessThan lbCount)
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
}
void printRightBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
if(rbCount greaterThan 0)
{
temp[index] = '(';
rbCount--;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
else
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
main()
{
lbCount = 0;
rbCount = 0;

printf("Enter the Number of Braces: ");
scanf(" %d",&rbCount);
lbCount = rbCount;
temp = (char *) malloc((rbCount+lbCount+1)*sizeof(char));
memset(temp,0,sizeof(temp));
printRightBrace(0);
}

5 comments:

Mad said...

Can u just give the algorithm in words than the program. It really helps in easy understanding

Mad said...

Let us write the combinations of 0's and 1's
Consider that 1 as '(' and 0 as ')'
The ones with the following constraints may succeed::
The number of 1's = The number of 0's
The sequence should start with 1 and end with 0
Given n as input . Get the sequence of all 2n sequences

For example if n = 3
000000
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
001101
001110
001111
010000
010001
010010
010011
010100
010101
010110
010111
011000
011001
011010
011011
011100
011101
011110
011111
All the above sequence can be ignored
100000 X
100001 X
100010 X
100011 X
100100 X
100101 X
100110
100111 X
101000 X
101001 X
101010
101011 X
101100
101101 X
101110 X
101111 X
110000 X
110001 X
110010
110011 X
110100
110101 X
110110 X
110111 X
111000
111001 X
111010 X
111011 X
111100 X
111101 X
111110 X
111111 X

Anonymous said...

@mad
i think ur algo will not work for all the cases consider the case-
n=4
10011100
())((())
wrong answer..

Anonymous said...

@mad
i think ur algo will not work for all the cases consider the case-
n=4
10011100
())((())
wrong answer..

Phani said...

for the above solution to work you may need to add 1 more case
correct me if i`m wrong
consider "(" =1 and ")" =-1

and the sum of series at any point should be more than 1..except for last char

in the above example 10011100
100=1+(-1)+(-1)=-1 so this is not a valid case