// Find Paranthesis Patterns - 
// Ex: 3 - () () (), () (()), (()) (), ((())), (() ())
//
#include <stdio.h>

// #define DEBUG_PRINT

int FindParanthesisPattern(char *pattern, int maxLength, int acWeight, int currLength);

int g_count = 0;

int main(int argc, char *args[])
{
  int maxLength, i;
  char*  pattern = NULL;

  printf("\n");

  for (i = 1; i < 10; i ++)
  {
    maxLength = i << 1; // Double the length to get the pattern length
    pattern = (char *) malloc((maxLength + 1) * sizeof(char));
    if (NULL == pattern)
    {
      printf("\nERROR: Not enough memory");
      return -1;
    }

    g_count = 0;
    FindParanthesisPattern(pattern, maxLength, 0, 0);

    free(pattern);

    printf("Pattern: Length = %d, Count = %d\n", i, g_count);
  }

  return 0;
}

int FindParanthesisPattern(char *pattern, int maxLength, int acWeight, int currLength)
{
  if (acWeight < 0) return 0;

  if (currLength == maxLength)
  {
    pattern[maxLength] = 0;
    if (0 == acWeight) 
    { 
#ifdef DEBUG_PRINT
      printf("Pattern: %s\n", pattern);
#endif
      ++g_count; 
    }
    return 0;
  }
  
  pattern[currLength] = '(';
  FindParanthesisPattern(pattern, maxLength, acWeight + 1, currLength + 1);

  pattern[currLength] = ')';
  FindParanthesisPattern(pattern, maxLength, acWeight - 1, currLength + 1);

  return 0;
}

Pattern: Length = 1, Count = 1
Pattern: Length = 2, Count = 2
Pattern: Length = 3, Count = 5
Pattern: Length = 4, Count = 14
Pattern: Length = 5, Count = 42
Pattern: Length = 6, Count = 132
Pattern: Length = 7, Count = 429
Pattern: Length = 8, Count = 1430
Pattern: Length = 9, Count = 4862