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);
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.