CareerCup

start with print ("", n, n); // 1st n is num of remaining opening braces and 2nd n is num of remaining closing braces.

void print (String s, int open, int closed) {
    if  (open = 0) {
       for (i = 0; i < closed; i++)  {
             s.append(")");
       }
       system.out.println(s);
       return;
    }

    print(s+"(", open -1, end);
    print (s+"()", open -1, end -1);

void printValidBrackets(int bracketsNum, char* outStr, int outStrLen, int completedBrackets)
{
for(int i = 1; (i + completedBrackets) <= bracketsNum; i++)
{
for(int j = 0; j < i; j++)
{
outStr[outStrLen + j] = '(';
}

for(j = 0; j < i; j++)
{
outStr[outStrLen + j + i] = ')';
}

outStr[outStrLen + 2*i] = '\0';

if((i + completedBrackets) == bracketsNum)
printf("%s\n",outStr);

printValidBrackets(bracketsNum, outStr, outStrLen + 2*i, completedBrackets + i);
}
}

We can do this recursively with only a few lines of code. There are a few rules that we need to take into consideration.

1) Counting from left to right, there are always more { than }. Therefore, { is always being generated first
2) There are only N { and }.
3) We can only generate } as long there are more {.

If you write code which obeys the above rules, your solution would be correct. It's only a few intuitive lines of code.

This is a constainted permuation problem:

do the permutation, and cut out the illegal cases!

void GenParen(int n){
//there are n * 2 curly braces
//there are n { and n }
char paren[n * 2]
GenParenH(&paren, n, 0, 0, 0);
}

void GenParenH(char *paren, int n, int lp, int rp, int index){
if (lp < n) {// if we haven't generated enough {
paren[index] = '{';
GenParenH(paren, n, l+1, r, index+1);
}

if (rp < lp) { //there are more { than }
paren[index] = '}';
GenParenH(paren, n, l, r+1, index+1);
}

}

Guys this can be done in O(n) time with O(n) space.

Use a stack -
1) For each '(' push onto stack
2) For each ')',
- if stack is empty, flash error as invalid input
- if stack is not empty, pop a '(' from stack.
3) At the end of parsing the input, if the stack is empty, input is valid, else invalid

The above code checks whether the output of Khoa's program is valid :)

void PrintValidBrackets(char* outStr, int current, int LeftTaken, int LeftLeft, int RightLeft){
if (!LeftLeft && !RightLeft) {
outStr[current]='\0';
std::cout<<outStr<<std::endl;
return;
}//base case

int RightTaken = LeftTaken+LeftLeft-RightLeft;
if(!LeftLeft){ //no left branket, only insert right brankets now
outStr[current]=')';
PrintValidBrackets(outStr,current+1,LeftTaken,LeftLeft,RightLeft-1);
return;
}

if (LeftTaken>RightTaken){ //already inserted more left brankets
outStr[current]=')'; // insert one right branket
PrintValidBrackets(outStr,current+1,LeftTaken,LeftLeft,RightLeft-1);
}

outStr[current]='('; // insert one left branket
PrintValidBrackets(outStr,current+1,LeftTaken+1,LeftLeft-1,RightLeft);
return;
}

This is very similar to the problem of printing all possible 3^7 results for 1-800-234-5678 number (replace 2 with characters a,b,c etc).

Start with a list of possible inputs, for n=3, you have (,(,(,),),). At each recursive step, pop out either "(" or ")" while making sure that its valid to do so and recusively call the same function to do the same for the rest of the inputs. Basically, you will end up recursively calling the funtion in a for loop at each step. Each time we reach the end of input list, we get a unique valid pattern.

a) Do usual permutation recursively
b) For each permutation check for matching brackects by usual push/pop stack based procedure

I haven't checked the other solutions posted above. Just implemented a clean recursive procedure - seems like what the others have come up.

#include <iostream>
#include <string>

using namespace std;


void print ( char *str, int leftRemaining, int rightRemaining ) {
  char *leftStringAppend, *rightStringAppend;
  leftStringAppend = new char [7];
  rightStringAppend = new char [7];
  strcat ( leftStringAppend , str );
  strcat ( leftStringAppend , "(" );
  strcat ( rightStringAppend , str );
  strcat ( rightStringAppend , ")" );
  if ( leftRemaining == 0 && rightRemaining == 0 ) {
    cout << str << endl;
    return;
  }
  else {
    if ( leftRemaining > 0 ) {
      print ( leftStringAppend , leftRemaining - 1 , rightRemaining );
    }
    if ( leftRemaining < rightRemaining ) {
      print ( rightStringAppend , leftRemaining , rightRemaining - 1 );
    }
  }
}


int main () {

  char *s = new char[15];

  print (s, 4, 4);

  return 0;

}

Something like a dynamic programming.

The nth result is all valid combinations of a single () pair with the n-1 th result.

catalan numbers

(2n)!
-------
(n+1)! n!

Code tested. It works

import java.util.*;
class genparen {
public static void main(String args[]){
genparen(3);
}
public static void genparen(int n){
int lp = 0; // use to keep track of whether the number of lp and rp are the same
helper(n, lp, "");
}
public static void helper(int n, int lp, String out){
// print out if there's no more lp left and it is balanced with rp
if (lp==0 && n == 0){
System.out.println(out);
// if it's not balanced yet, print out more ")"
} else if (n == 0) {
helper(n, lp-1, out+")");
// if it's balanced, but there are still more lp, add more lp to the output string
} else if (lp==0) {
out += "(";
helper(n-1, 1, out);
} else {
// add more lp
helper(n-1, lp+1, out+"(");
// add more rp
helper(n, lp-1, out+")");
}
}
}

Simualting a stack using recursion.
First push a {;
then either push one or pop one.

recursive solution without any crapy character arrays
(works for # of parenth < 32, I bet no one can enumerate
all combinations with more than 32 pars):

int n_total = 6; // total number of parenthesis
char par[] = {')','('};

void parenth(int n_open, int n_closed, int num) {

    if(n_closed == n_total) {
        int mask = 1 << (2*n_total-1);            
        while(mask) {
            putchar(par[num & mask ? 1 : 0]);
            mask >>= 1;
        }
        putchar('\n');
        return;
    }
    
    num *= 2;
    if(n_closed < n_open) // closing parenth encoded as 0
        parenth(n_open, n_closed + 1, num);
     
    if(n_open < n_total) // opening parenth as 1
        parenth(n_open + 1, n_closed, num + 1);
}

main() {
   parenth(0, 0, 0);
}

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> bra_strs(int dep)
{
vector<string> res;
if (dep == 0)
res.push_back("");
else if (dep==1)
res.push_back("()");
else
{
vector<string> less_strs = bra_strs(dep-1);
res.push_back("()"+less_strs[0]);
res.push_back("("+less_strs[0]+")");
for (int i=1; i<less_strs.size(); i++)
{
res.push_back("()"+less_strs[i]);
res.push_back("("+less_strs[i]+")");
res.push_back(less_strs[i]+"()");
}
}
return res;
}


int main()
{
vector<string> res= bra_strs(4);
cout<<"Number of combinations"<<res.size()<<endl;
for (int i=0; i<res.size(); i++)
cout<<res[i]<<endl;

}

I think the best solution can be achieved using dynamic programming:
the idea is:

a valid combination of brackets 'VALID' = { '(' VALID ')' , '(' ')' VALID }
just two of it. And the base case of VALID is only with '(' and ')'
so just call a recursive routine and solve :)

follow the idea of vodangkhoa:

void geneString(char arr[], int n, int left, int right, int pos)
{
if (left == n&& right == n) {
for (int i=0; i< 2*n; i++)
cout << arr[i];
cout << endl;
return;
}
if (left < n) {
arr[pos] = '(';
geneString(arr,n,left+1,right,pos+1);
}
if (right < left) {
arr[pos] = ')';
geneString(arr,n,left,right+1,pos+1);
}
}

Hi,

how about this approach?

If we see the opening brackets.... The possible combinations for the start of the string in the question are all 3 openings brackets, 2 opening brackets and then one opening bracket. Thus for each of the case we generate the starting strings... ie (((, ((, ( for n=3. Then for each of the string we append ")(" as long as the count of each of the brackets is less than 3.

Thus for the first case of (((, we have exhausted the count of 3 for ( so all we do is append the remaining 3 closing brackets ))).

For the second case (( ')(' )) == (()())

For the third case (')(' ')('') == ()()()

Please tell me if I missed something.

The basic algo is:
=======================================
void foo(string s, int n)
{
....if(n==0)
.......cout<<s<<endl;
.......else{
............foo("()"+s, n-1);
............foo('('+s+')', n-1);
............foo(s+"()", n-1);
.......}
}

int main(){
.....foo("", 3);
}
====================================
The you might realize that this code does not work perfectly because where "()" interleaves, such as "", "()",and "()()()",
"()"+s looks the same as s+"()". Therefore, this special case should be addressed by using only s+"()" once. Finding this special case might cost more codes than the algo itself. :)

For recursion, when each level might generate (return) multiple values: such as:
1. "()"+s
2. s+"()"
3. '('+s+')'
=====================
Then process these values (usually process=cout in this situation) at the leaf level, rather than return all the values to the root level. Because return all the values to its parent level is impossible.

Yes, catalan number, and recursion will do the job

#include <vector>
#include <iostream>
using namespace std;
void print(vector<int>& bs)
{
	for(int i=0;i<bs.size();i++)
		cout<<bs[i];
	cout<<endl;
	for (int i=0;i<bs.size();i++)
	{
		cout<<'(';
		for(int j=0;j<bs[i];j++)
			cout<<')';
	}
	cout<<endl;
}
void brackets(int n, int rest, int allow, vector<int>& arrange)
{
	if(arrange.size()==n-1)
	{
		arrange.push_back(rest);
		print(arrange);
		return;
	}
	for(int i=0;i<=allow&&i<=rest;i++)
	{
		vector<int> newvector(arrange.begin(),arrange.end());
		newvector.push_back(i);
		brackets(n,rest-i,allow+1-i,newvector);
	}
}
int main()
{
	vector<int> v;
	int n; cin>>n;
	brackets(n,n,1,v);
	return 0;
}

void doPrintPar(string &par, int a, int b, int &number)
{
if((a==number) && (b==number))
cout << par.c_str() << endl;
else if(a>b)
{
if(a<number)
{
par.append("(");
doPrintPar(par, a+1, b, number);
par.erase(par.length()-1,1);
par.append(")");
doPrintPar(par, a, b+1, number);
par.erase(par.length()-1,1);
}
else
{
par.append(")");
doPrintPar(par,a,b+1,number);
par.erase(par.length()-1,1);
}
}
else if(a==b)
{
par.append("(");
doPrintPar(par,a+1,b,number);
par.erase(par.length()-1,1);
}
}
void printParenthesis(int number)
{
string par;
int a=0;
int b=0;

doPrintPar(par, a, b, number);
}

void doPrintPar(string &par, int a, int b, int &number)
{
if((a==number) && (b==number))
cout << par.c_str() << endl;
else if(a>b)
{
if(a<number)
{
par.append("(");
doPrintPar(par, a+1, b, number);
par.erase(par.length()-1,1);
par.append(")");
doPrintPar(par, a, b+1, number);
par.erase(par.length()-1,1);
}
else
{
par.append(")");
doPrintPar(par,a,b+1,number);
par.erase(par.length()-1,1);
}
}
else if(a==b)
{
par.append("(");
doPrintPar(par,a+1,b,number);
par.erase(par.length()-1,1);
}
}
void printParenthesis(int number)
{
string par;
int a=0;
int b=0;

doPrintPar(par, a, b, number);
}

void doPrintPar(string &par, int a, int b, int &number)
{
if((a==number) && (b==number))
cout << par.c_str() << endl;
else if(a>b)
{
if(a<number)
{
par.append("(");
doPrintPar(par, a+1, b, number);
par.erase(par.length()-1,1);
par.append(")");
doPrintPar(par, a, b+1, number);
par.erase(par.length()-1,1);
}
else
{
par.append(")");
doPrintPar(par,a,b+1,number);
par.erase(par.length()-1,1);
}
}
else if(a==b)
{
par.append("(");
doPrintPar(par,a+1,b,number);
par.erase(par.length()-1,1);
}
}
void printParenthesis(int number)
{
string par;
int a=0;
int b=0;

doPrintPar(par, a, b, number);
}

void doPrintPar(string &par, int a, int b, int &number)
{
if((a==number) && (b==number))
cout << par.c_str() << endl;
else if(a>b)
{
if(a<number)
{
par.append("(");
doPrintPar(par, a+1, b, number);
par.erase(par.length()-1,1);
par.append(")");
doPrintPar(par, a, b+1, number);
par.erase(par.length()-1,1);
}
else
{
par.append(")");
doPrintPar(par,a,b+1,number);
par.erase(par.length()-1,1);
}
}
else if(a==b)
{
par.append("(");
doPrintPar(par,a+1,b,number);
par.erase(par.length()-1,1);
}
}
void printParenthesis(int number)
{
string par;
int a=0;
int b=0;

doPrintPar(par, a, b, number);
}

when n = 3, isn't (()()) also a valid combination?

This one works:

void generatePattern(char *braces, int index, int open, int close, const int n)
{
    if (n == close)
    {
        for (int i = 0; i < n * 2; i++)
            std::cout << braces[i];
        std::cout << '\n';
        return;
    }
    if (open < n)
    {
        braces[index] = '(';
        generatePattern(braces, index + 1, open + 1, close, n);
    }
    if (close < open)
    {
        braces[index] = ')';
        generatePattern(braces, index + 1, open, close + 1, n);
    }
}

bracket(int n1,int n2,char brkt)/*here when first time function is called brkt contains '{' and n1 is n-1 and n2 is n*/
{
if(n1==0 and n2==0)
return;
else if(n1==0&&brkt=='{')
return;
else {
print(brkt);
return( bracket(n1-1,n2,'{')||bracket(n1,n2-1,'}'));
}
}