CareerCup

I guess this can be or should be done using DP. assume that we have kept the left parts of all the parentheses now we are suppose to place the right part of the n parentheses,
therefore we start by placing ) at the last and keeping all the entries or strings in a hashmap, for checking if we have already made/visited a particular combination. Now the second ")" can be placed at 3 positions i.e. last, 2nd last, 3rd last out of which last and second last will be same so only one entry will go in the map. Similarly we will keep doing this for all other remaining ")" parantheses, and at the end count/print all Strings in the hashmap which have length 2n.

public class Parantheses {
	public static void  main(String[] args){
		long t1 = System.currentTimeMillis();
		int n = 13;
		HashSet<String> entry = new HashSet<String> ();
		(new Parantheses()).calc("(((((((((((((" , entry, n, 1);
		Iterator itr = entry.iterator();
		while(itr.hasNext()){
			String ent = (String)itr.next();
			//if(ent.length()==2*n)
				//System.out.println(ent);
		}
		long t2 = System.currentTimeMillis();
		System.out.println(t2-t1);
	}
	
	
	public void calc(String current, HashSet<String> entry, int n, int curr){
		if(n < curr)
		return;
		for(int i = current.length()-2*(curr-1);i<=current.length();i++){
			String temp = current.substring(0,i) + ")" + current.substring(i);
			if(!entry.contains(temp)){
				entry.add(temp);
				calc(temp, entry, n, curr + 1);
			}
		}		
	}
}

Let no = No.of open parentheses used,

func perm_gen(N, no, max_close, output_str){
    if(no == N){
         output_str 
         print output_str.append(")"*max_close);
         return;
    }
    if(max_close > 0)
         perm_gen(N, no, max_close--, output_str.append(')'));
    perm_gen(N, no+1, max_close+1, output_str.append('('));
}

func main(){
    perm_gen(N, 0, 0, "");
}

<pre lang="" line="1" title="CodeMonkey89374" class="run-this">int printParentheses(char *curStr, int n, char *str, int sm)
{
if (NULL == str || NULL == curStr)
return 0;

if (0 == sm)
{
printf("%s\n",str);
return 0;
}

for (int i = 0;i < n;i++)
{
*curStr = '(';
*(curStr+(2*i+1)) = ')';
printParentheses(curStr+1,i,str,sm-1);
if (0 == sm-1-i)
continue;
printParentheses(curStr+(2*(i+1)),n-1-i,str,sm-1-i);
}
return 0;
}
</pre><pre title="CodeMonkey89374" input="yes">
</pre>

void printParenthese(unsigned n)
{
char *output = new char[2n+1];
if (output == null)
{
return;
}
output[2n] = null;

doPrint(output, 0, n, n);
}

void doPrint(char *output, unsigned i, unsigned left, unsigned right)
{
if (right == 0)
{
sprintf("%s", output);
return;
}

if (left < right)
{
output[i] = ')';
doPrint(output, i+1, left, right-1);
}
if (left > 0)
{
output[i] = '(';
doPrint(output, i+1, left-1, right);
}
}

Add 1 last line in printParenthese():
delete[] output;

void func(string s, int len, int state){
    if(s.length() == len*2){
	if(state == 0)
	    cout << s << endl ;
	return ;
    }
    if(state == 0)
	func(s + '(', len, 1) ;
    else{
	if(state < len)
	    func(s + '(', len, state + 1) ;
	if(state > 0)
	    func(s + ')', len, state - 1) ;
    }
}

int main(){
    string s = "" ;
    func(s, 4, 0) ;
}

I found this on Stack Overflow and it looks like the best solution for this problem. I couldn't come up with it on my own, so credit to Vallabh Patade.

public static void main(String[] args) {
        printParenthesis(3);
    }
    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);
    }

not sure what the complexity is though.