PROGRAMMING INTERVIEWS

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

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