CareerCup

string PerfectParanth(int openP, int closeP, int totalPair, string resultSoFar)
{
       string tmp1, tmp2 = "";
       if ( totalPair == closeP )
           return resultSoFar;
       if ( openP < totalPair )
           tmp1 += PerfectParanth(openP + 1, closeP, totalPair, resultSoFar + "(");
       if ( openP > closeP )
           tmp2 += PerfectParanth(openP, closeP + 1, totalPair, resultSoFar + ")");
        return tmp1 + tmp2;
}

void print(int n,String currentStrring,int k){
if(n==0&& k==0)
cout<<currentString;
else{
print(n-1,currentString+'(',k+1);
print(n-1,currentString+')',k-1);
}

This is 1 variation of Dyck language

http : // en . wikipedia . org / wiki / Catalan_number //remove spaces

chck the recurrence relation given in this page...

hey siva.sai
cn u pls share d amazon's written test questions...

static void main()
{
Braces("",3);

}
static void Braces(String str, int number)
{
System.out.print(str+ReturnBraces(number));
System.out.print(",");
int i = number;
while(i>1)
{
i--;
Braces(str+ReturnBraces(number-i),i);
}
}

static String ReturnBraces(int num)
{
String retString = "";
for(int i=0; i<num; i++)
retString = "("+retString+")";
return retString;
}

<pre lang="c" line="1" title="CodeMonkey49153" class="run-this">
#include<stdio.h>
void printBrackets(char* partial, int curpos,int left, int total_pairs, int right)
{
if(left < total_pairs)
{
partial[curpos]='(';
printBrackets(partial, curpos+1, left+1, total_pairs, right);
partial[curpos] = '\0';

}
if(right < left)
{
partial[curpos]=')';
if(right+1 == total_pairs)
{
partial[curpos+1] = '\0';
printf("%s\n", partial);
return;
}
else
{
printBrackets(partial, curpos+1, left, total_pairs, right+1);
partial[curpos]='\0';
}
}
}
void main()
{
int pairs=0;
char s[100];

#include<stdio.h>
void printBrackets(char* partial, int curpos,int left, int total_pairs, int right)
{
if(left < total_pairs)
{
partial[curpos]='(';
printBrackets(partial, curpos+1, left+1, total_pairs, right);
partial[curpos] = '\0';

}
if(right < left)
{
partial[curpos]=')';
if(right+1 == total_pairs)
{
partial[curpos+1] = '\0';
printf("%s\n", partial);
return;
}
else
{
printBrackets(partial, curpos+1, left, total_pairs, right+1);
partial[curpos]='\0';
}
}
}
void main()
{
int pairs=0;
char s[100];
s[0]='\0';
printf("How many pairs:");
scanf("%d", &pairs);

printBrackets(s, 0, 0, pairs, 0);
}</pre><pre title="CodeMonkey49153" input="yes">3</pre>

<pre lang="c" line="1" title="CodeMonkey34278" class="run-this">
#include<stdio.h>
void printBrackets(char* partial, int curpos,int left, int total_pairs, int right)
{
if(left < total_pairs)
{
partial[curpos]='(';
printBrackets(partial, curpos+1, left+1, total_pairs, right);
partial[curpos] = '\0';

}
if(right < left)
{
partial[curpos]=')';
if(right+1 == total_pairs)
{
partial[curpos+1] = '\0';
printf("%s\n", partial);
return;
}
else
{
printBrackets(partial, curpos+1, left, total_pairs, right+1);
partial[curpos]='\0';
}
}
}
void main()
{
int pairs=0;
char s[100];

#include<stdio.h>
void printBrackets(char* partial, int curpos,int left, int total_pairs, int right)
{
if(left < total_pairs)
{
partial[curpos]='(';
printBrackets(partial, curpos+1, left+1, total_pairs, right);
partial[curpos] = '\0';

}
if(right < left)
{
partial[curpos]=')';
if(right+1 == total_pairs)
{
partial[curpos+1] = '\0';
printf("%s\n", partial);
return;
}
else
{
printBrackets(partial, curpos+1, left, total_pairs, right+1);
partial[curpos]='\0';
}
}
}
void main()
{
int pairs=0;
char s[100];
s[0]='\0';
printf("How many pairs:");
scanf("%d", &pairs);

printBrackets(s, 0, 0, pairs, 0);
}</pre><pre title="CodeMonkey34278" input="yes">3</pre>

pardon the last two comments. Went out of hand. I was playing with the runnable code interface in this page

<pre lang="c" line="1" title="CodeMonkey89021" class="run-this">#include<stdio.h>
void printBrackets(char* partial, int curpos,int left, int total_pairs, int right)
{
if(left < total_pairs)
{
partial[curpos]='(';
printBrackets(partial, curpos+1, left+1, total_pairs, right);
partial[curpos] = '\0';

}
if(right < left)
{
partial[curpos]=')';
if(right+1 == total_pairs)
{
partial[curpos+1] = '\0';
printf("%s\n", partial);
return;
}
else
{
printBrackets(partial, curpos+1, left, total_pairs, right+1);
partial[curpos]='\0';
}
}
}
void main()
{
int pairs=0;
char s[100];
s[0]='\0';
printf("How many pairs:");
scanf("%d", &pairs);

printBrackets(s, 0, 0, pairs, 0);
}</pre><pre title="CodeMonkey89021" input="yes">3</pre>

char str[100];


void findBracket(char *s,int open, int close)
{
if(open==0)
{
for(int i=0;i<close;i++)
{
strcat(s,")");
}
printf("%s\n",s);
return;
}

//close a bracket and then open another
if(close>open)
{
char * temp1 = new char[100];
strcpy(temp1,s);
strcat(temp1,")");
findBracket(temp1,open,close-1);
delete temp1;
}

//or open another bracket
char * temp2 = new char[100];
strcpy(temp2,s);
strcat(temp2,"(");
findBracket(temp2,open-1,close);
delete temp2;
}


int main()
{
strcpy(str,"");
findBracket(str,3,3);
}

i think all of the above programs are printing the complete answers..
for example if
if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...

none of the code is printing the entire solution...correct me if am wrong...

typo error in the previous comment..sorry...

i think none of the above programs are printing the correct answers..
for example if
if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...

none of the code is printing the entire solution...correct me if am wrong...

Its an application of catalon numbers. I am also writing down the working code.

// function to generate parantheses for a given N
// open : number of open parentheses placed
// closed : number of closed parentheses placed
// N : the input number
// str : the char buffer of 2*N size
// len : current length of str
void generate_parantheses(size_t open, size_t close, size_t N, char* str, size_t len)
{
if(open < close)
return;

if(open + close == N*2)
{
str[len++] = '';
std::cout<<str<<"\n";
return;
}

if(open < N)
{
str[len++] = '(';
generate_parantheses(open+1, close, N, str, len);
str[--len] = ' ';
}

if(close < N)
{
str[len++] = ')';
generate_parantheses(open, close+1, N, str, len);
str[--len] = ' ';
}
}

void main()
{
size_t N = 6;

char *buffer = new char[2*N+1];

generate_parantheses(0, 0, N, buffer, 0);

delete []buffer;
}

public class TestBrace
{
public static void main(String[] args)
{
int N = 3;
getBraceString(N, N, N, "");

}

static int count = 1;

public static void getBraceString(int left, int right, int N, String current)
{

if (left == 0 && right == 0)
{
System.out.println(count++ + " " + current);
return;
}

if (left > 0)
{
getBraceString(left - 1, right, N, current + "(");
}

if (left < right)
{
getBraceString(left, right - 1, N, current + ")");
}
}

}

#include<stdio.h>
#include<string.h>

struct StringBraces {
	char str[30];
	int open;
};


void printCombinations(int num, int count, struct StringBraces strbr)
{
	int len,cnt;
	len=strlen(strbr.str);
	if(num==0)
	{
		printf("%s\n",strbr.str);
		return;
	}	
		if (strbr.open>0) {
			if(strbr.open<num)
			{
			strbr.str[len]='(';
			strbr.str[len+1]='\0';
			strbr.open++;
			printCombinations(num-1,count,strbr);
			strbr.open--;
			}
			
			while (strbr.open>0) {
				strbr.str[len]=')';
				len++;
				num--;
				strbr.open--;
			}
			strbr.str[len]='\0';
			
			printCombinations(num,num,strbr);
			
		}
		else {
			strbr.str[len]='(';
			strbr.str[len+1]='\0';
			strbr.open++;
			printCombinations(num-1,count,strbr);
		}
	
	
}


int main()
{
	int num;
	struct StringBraces strbr;
	printf("Give number");
	scanf("%d",&num);
	strbr.open=0;

	if(num%2==0)
	printCombinations(num,num,strbr);
	else {
		printf("Needed Even number\n");
	}


	return 0;
}