Question: Print all valid parenthesis Sequences for a given number of pairs of parenthesis.

Example:
For n =2 {}{}, {{}}
For n = 3 {{{}}}, {}{}{}, {{}}{}, {}{{}}, {{}{}}

Answer: If you have heard about Catalan number, you might know that number of valid sequences are ((2n)!)/((n+1)! * n!)

Algo:

func(len)

//Input:
//length: current length of string formed

//Output:
//Whenever a result is found display() function is called

if(len = 2*n)
____display(out)
____return;

out[len] = '(' //Append ( to out
if(isValid(s1))
____func(len+1)

out[len] = ')' //Append ( to out
if(isValid(s1))
____func(len+1)

Code

```
#include <stdio.h>
#define N 4 //Number of parenthesis pair

int n;
char out[N *2+1] = {0};

bool isvalid(int len)
{
int open, close, i;
open = close = 0;
for (i = 0; i <= len; i++)
{
if (out[i] == '(')
open++;
else
close++;

if ((open < close) || (open > N))
return false;
}
return true;
}

void generate(int len)
{
if (len == (N *2))
{
printf("%s\n", out);
return ;
}
out[len] = '(';
if (isvalid(len))
generate(len + 1);

out[len] = ')';
if (isvalid(len))
generate(len + 1);
}

int main()
{
generate(0);
return 0;
}```

But this solution has a lot of overhead of isvalid() function. If we can check the validity of sequence in generate() itself by passing 'open' and 'close' count, this overhead can be reduced a lot. Below is a modified and more efficient program for the same.

```
#include <stdio.h>
#define N  4  //Number of parenthesis pair

int n = N;
char out[2 *N + 1] = { 0, };

void printbracket(int level, int open, int close)
{
if (level == 2 *n)
{
printf("%s\n", out);
return ;
}

out[level] = '(';
if ((open + 1) <= n && open >= close)
{
printbracket(level + 1, open + 1, close);
}

out[level] = ')';
if ((close + 1) <= n && open >= close)
{
printbracket(level + 1, open, close + 1);
}
}

main()
{
printbracket(0, 0, 0);
}```