#include <stdio.h>
#include <stdlib.h>
int total=0;
void bracket(char a[],int n,int pairsComplete,int bracketOpen,int index);
int main()
{
  char array[20], n = 4;
  bracket(array,n,0,0,0);
  //printf("Total ways : %d \n",total);
  return 0;
}
void bracket(char a[],int n,int pairsComplete,int bracketOpen,int index)
{
  if(pairsComplete == n)
  {
    int i=0;
    for(i=0;i < 2*n;i++)
    {
      printf("%c",a[i]);
    }
    printf("\n");
    return;
  }
  if((pairsComplete + bracketOpen) == n) // cannot open another bracket
  {
    a[index] = '}';
    bracket(a,n,pairsComplete+1,bracketOpen-1,index+1);
  }
  else if(bracketOpen == 0) // cannot put a closing bracket
  {
    a[index] = '{';
    bracket(a,n,pairsComplete,1,index+1);
  }
  else
  {
    a[index] = '{';
    bracket(a,n,pairsComplete,bracketOpen+1,index+1);
    
    a[index] = '}';
    bracket(a,n,pairsComplete+1,bracketOpen-1,index+1);
  }
}