CareerCup

static void printParenthesis(int n){
		printParenthesis("",n,n);
		
	}
	
	static void printParenthesis(String s,int open,int close){
		if(open>close)
			return;
		if(open == 0 && close == 0){
			System.out.println(s);
			return;
		}
		if(open < 0 || close<0)
			return;
		
		printParenthesis(s + '{',open-1,close);
		printParenthesis(s + '}',open,close-1);
	}

Print(char a[], int n, int open,int close,int i)
{
if(close==n)
{
print(a)
return;
}
if(close<open)
{
a[i]=")";
Print(a,n,open,close+1,i+1);
}
if(open<n)
{
a[i]="(";
Print(a,n,open+1,close,i+1);
}
}

This one uses a lot of memory but it's easy to see the core logic.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class ParenthesisCombination {

	static final String LP = "{";
	static final String RP = "}";

	public static void main(String[] args) {
		int n = 10;
		printCombinations(n);
	}

	static void printCombinations(int n){
		List<String>list=getCombinations(n);
		int i=1;
		for(String s:list)
			System.out.println(i+++"\t"+s);
	}
	
	static List<String> getCombinations(int n){
		HashMap<Integer,List<String>>map=new HashMap<Integer, List<String>>();
		for(int i=1;i<=n;i++){
			List<String>newlist=new ArrayList<String>();
			if(i==1){
				newlist.add(LP+RP);
			}
			else{		
				List<String>list=map.get(i-1);
				for(String s:list){
					newlist.add(LP+RP+s);
					newlist.add(LP+s+RP);
				}
			}
			map.put(i,newlist);
			map.remove(i-1);
		}
		return map.get(n);
	}

}

This doesn't have the memory overhead.

public class ParenthesisCombination {

	static final char LP = '{';
	static final char RP = '}';
	static final char NULL='\u0000';

	public static void main(String[] args) {
		int n = 3;
		char[]c=new char[n*2];
		printCombinations(n,c,0,c.length-1,0);
	}
	
	static void printCombinations(int n,char[]c,int start, int end, int count){
		if(start>=end)
			return;
		
		count+=2;
		
		c[start]=LP;
		c[start+1]=RP;
		printCombinations(n-1,c,start+2,end,count);
		
		if(count==c.length)
			print(c);
		
		if(n==1) //when n=1 there is only one side
			return;
		
		c[start]=LP;
		c[end]=RP;
		printCombinations(n-1,c,start+1,end-1,count);
		
		if(count==c.length)
			print(c);
		
	}
	
	static void blankOut(char[]c,int start,int end){
		for(int i=start;i<=end;i++)
			c[i]=NULL;
	}
	
	static void print(char[]c){
		for(int i=0;i<c.length;i++)
			System.out.print(c[i]);
		System.out.println();
	}	
}

char* result = new char[2*n];
result[0] = '{';
result[2*n-1] = '}';

for( i = 1; i <= 2*n; i++ )
	if( i <= n )
		a[i-1] = '{';
	else
		a[i-1] = '}';
print(result);

while( 1 )
{

	if( a[2*n-2] == '{' && a[1] == '{' }
		break;
	
	validator = 0;
	countopen = 0;
	countclose = 0;
	i = 2*n-2;
	do
	{
		if( a[i] == '{'
			validator++;
			countopen++;
		else
			validator--;
			countclose++;
		i--;
	}while( a[i] != '{' );
	
	countopen = n - countopen;
	countclose = n - countclose;
	validator = -validator;
	
	a[i++] = '}';

	validator -= 2;
	countopen--;
	countclose++;
	
	while( i != 2n-2 )
	{
		if( validator+1 <= n && countopen+1 <= n )
			validator++;
			countopen++;
			a[i++] = '{';
		else
			validator--;
			countopen--;
			a[i++] = '}';
	}
	print(result);
}

#include<iostream>
using namespace std;
void f(char* arr,int left,int right,int top)
{
if(left<=right && left>0)
{
arr[top]='(';arr[top+1]='\0';
f(arr,left-1,right,top+1);
}
if(left<right && right>0)
{
arr[top]=')';arr[top+1]='\0';
f(arr,left,right-1,top+1);
}
if(left==0 && right==0)
cout<<arr<<endl;
}
int main()
{
int n;
char arr[1000];
cin>>n;
f(arr,n,n,0);
}

#include<iostream>
using namespace std;
void f(char* arr,int left,int right,int top)
{
if(left<=right && left>0)
{
arr[top]='(';arr[top+1]='\0';
f(arr,left-1,right,top+1);
}
if(left<right && right>0)
{
arr[top]=')';arr[top+1]='\0';
f(arr,left,right-1,top+1);
}
if(left==0 && right==0)
cout<<arr<<endl;
}
int main()
{
int n;
char arr[1000];
cin>>n;
f(arr,n,n,0);
}

void mainfunc(int n)
{
   char* s = new char[n*2 + 1];
   s[n*2] = '\0';

   f(n, n, s, 0, 0);
}

void f(int cLeft, int cRight, char* s, int idxS, int leftToMatch)
{
    if(cRight == 0)
    {  
        printf("%s\n", s);
        return;
    }  

    if(cleft != 0)
    { 
       s[idxS+1]='(';
       f(cLeft-1, cRight, s, idxS+1, leftToMatch+1);
    }

    if(leftToMatch!=0)
    {
        s[idxS+1] = ')';
        f(cLeft, cRight-1,s,idxS+1,leftToMatch-1);
    }    
}

We should draw a tree to analyze the cases. Suppose we want to enumerate 3 pairs.

(
                         ((                                     ()
               (((                    (()                      ()(
               ((()            (()(       (())         ()((         ()()
               ((())           (()()      (())(       ()(()        ()()(
               ((()))          (()())     (())()     ()(())       ()()()

Let left and right denote the number of left and right parenthesis needed. The base case is shown on the leaf level, when right == 0; otherwise we need call parenthesis_match recursively on the following cases:

1.  if (left == right) {
       add "("
       parenthesis_match(left - 1, right);
     } else if (left < right && left != 0) {
       add "("
       parenthesis_match(left - 1, right);
       remove "("
       add ")"
       parenthesis_match(left, right - 1);
     } else if (left == 0) {
       add ")"
       parenthesis_match(left, right - 1);
     }

PrintBrackets(int count)
{
int i = count;

while(i>0)
{
Print('{;, i);
Print('};, i);
PrintBrackets(count - i);
}
}

Print(char bracket, int count)
{
for(i=0; i<count; i++)
{
cout<<bracket;
}
}

Approach:
n=1 { }
n = 2 { } { } and {{ }}
for any n ... just need to put bracket in start and end of previous n result and one {} in start of all
like n = 3
{ {} {} },

and {} {} {}, {}{{}}
i will share the code for it ASAP