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:

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

    ReplyDelete
  2. 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

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

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

    ReplyDelete
  5. 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

    ReplyDelete