CareerCup

The code prints all forms without duplicates. This question (solution) is in "Cracking the coding interview" Book.

def paren(left,right,string):
    if(left == 0 and right == 0):
        print string
    if(left>right):
        return
    if (left > 0):
        paren(left-1,right,string+"(")
    if (right > 0):
        paren(left,right-1,string+")")

def parentheses(n):
    paren(n/2,n/2,"")

parentheses(6)

output:
((()))
(()())
(())()
()(())
()()()

C version:

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

int n, kind;
char s[MAX*2+1];
/*
    we can recursively determine next character of the string
    if left < n
        we can choose to use one more left parenthesis or not
    if right < left
        we use one more right parenthesis
*/
void print(char* dest, int left, int right)
{
    if(left == n && right == n){
        puts(dest);
        ++kind;
        return;
    }
    if(left < n){
        dest[left+right] = '(';
        print(dest, left+1, right);
    }
    if(right < left){
        dest[left+right] = ')';
        print(dest, left, right+1);
    }
}

int main()
{   
    while(scanf("%d", &n), n){
        s[n<<1] = '\0';
        kind = 0;
        print(s, 0, 0);
        printf("%d kinds in total\n", kind);
    }
    
    return 0;
}

Recursive version.

Keep track of how many open and close brackets are remaining.

Also keep track of number of open - number of closed used so far (called the balance_factor).

Python code:

def paren(num_open, num_close, balance_factor, paren_list):
    if num_open + num_close == 0:
        print "".join(paren_list)
        return
   
    if balance_factor > 0 and num_close > 0:
        paren_list.append(")")
        paren(num_open, num_close-1, balance_factor-1, paren_list)
        paren_list.pop()
   
    if num_open > 0:
        paren_list.append("(")
        paren(num_open -1, num_close, balance_factor+1, paren_list)
        paren_list.pop()
    
def paren_gen(n):
    print "n =", n
    paren(n, n, 0, [])
    print "-----"
  
def main():
    paren_gen(2)
    paren_gen(3)
    paren_gen(4)
  
if __name__ == "__main__":
	main()

output

n = 2
()()
(())
-----
n = 3
()()()
()(())
(())()
(()())
((()))
-----
n = 4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))
-----

The code above looks correct. I am still posting the java version I wrote using a similar approach. The recursive implementation is in fact dynamic programming.

public class ParanthesisSequence {    
    public static void GetSequence(int N, int nClose) {
        if (N == 0) {
            sequences.add(a_sequence);
            return;
        }
        if (nClose == 0) {
            // We don't have to close any paranthesis since there are no open ones
            a_sequence = a_sequence + "(";
            GetSequence(N - 1, 1);
        }
        if (nClose > 0) {
            if (N >= nClose + 2) {
                // We could still open paranthesis
                String temp = a_sequence;
                a_sequence = a_sequence + "(";
                GetSequence(N - 1, nClose + 1);
                a_sequence = temp;
            }
            a_sequence = a_sequence + ")";
            GetSequence(N - 1, nClose - 1);
        }
    }
    
    private static String  a_sequence = "";
    public static ArrayList<String> sequences;
}

Sample usage:

public static void main(String[] args) {
        // TODO code application logic here
        int N = 6; // N = 2 * n
        ParanthesisSequence.sequences = new ArrayList<String>();
        ParanthesisSequence.GetSequence(N, 0);
        for (String s : ParanthesisSequence.sequences) {
            System.out.println(s);
        }
    }

Output:

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

class NBrackets{

	public static void main( String[] args ){
		sumCombination( "", Integer.parseInt( args[0] ) );
	}

	static void sumCombination( String output, int sum ){
		if( sum == 0 ) {
			generateOutput( output );
			return;
		}
	
		for( int i = 1; i <= sum; i++ ){
			sumCombination( output + i, sum - i );
		}
	}
	
	static void generateOutput( String output ){
		StringBuilder builder = new StringBuilder();
			
		for( int i = 0; i < output.length(); i++){
			char c = output.charAt( i );
			builder.append( toBrackets( c - 48 ) );
		}
		
		System.out.println( builder.toString() );
	}
	
	static String toBrackets( int n ){
		StringBuilder builder = new StringBuilder();
		for( int i = 0; i < n; i ++ ){
			builder.append( "(" );
		}
		for( int i = 0; i < n; i ++ ){
			builder.append( ")" );
		}
		
		return builder.toString();
	}
}

Python code below:

def R(n, buf=''):
    if len(buf) == 2*N:
        print buf

    if n > 0:
        buf += ')'
        R(n-1, buf)
        buf=buf[:-1]

    if 2*N - (n+len(buf)) >= 2:
        buf += '('
        R(n+1, buf)
        buf=buf[:-1]


N = 4
R(0)

#include<stdio.h>
#include<stdlib.h>
void printParanthesis(char *str,int index,int num,int open,int close)
{
  if( open==close&&open==num)
  {
   printf("\n %s",str);
     return;
  }
   
   if(open<num)
{
 
str[index]='(';
   printParanthesis(str,index+1,num,open+1,close);

}
 
   if(open>close)
  {
    
     str[index]=')';
     printParanthesis(str,index+1,num,open,close+1);

   }
}
int main()
{

char str[50]={'\0'};
 printParanthesis(str,0,3,0,0);


}

Another C Program using "BackTracking"

#include<stdio.h>


#define MAXN 100
#define MAXC 3

char a[MAXN];
char c[MAXC];

int is_solution(char a[], int k, int n)
{
  return (k == n-1);
}

void process_solution(char a[], int k, int n)
{
  a[k+1] = '\0';
  printf("\n%s",a);
}

int construct_candidates(char a[], int k, int n, char c[])
{
  int nopen = 0;
  int nclosed = 0;
  int ncandidates = 0;

  int i=0;
  for(i=0;i<k;i++)
  {
    if( a[i] == '(' )
    {
      nopen++;
    }
    else 
      if(a[i] == ')' )
      {
        nclosed++;
      }
  }

  if( nopen < (n>>1) )
    c[ ncandidates++] = '(';

  if( nclosed < nopen )
    c[ ncandidates++] = ')';

  return ncandidates;
}


void backtrack(char a[], int k, int n)
{
  if( is_solution( a,k, n ) )
  {
    process_solution(a,k,n);
    return;
  }
  else
  {
    char c[MAXC];
    k = k+1;
    int ncandidates = construct_candidates(a,k,n,c);
    int i = 0;
    for(i=0; i<ncandidates; i++)
    {
      a[k] = c[i];
      backtrack(a,k,n);  
      a[k] = '\0';
    }
  }
}

int main()
{
  int n; 
  scanf("%d",&n);
  backtrack(a,-1,n<<1);
  printf("\n");
}

public static void generateValidParanthesis(int n, String s) {
		if(n == 0) { System.out.println(s); return; }
		
		
		String s1 = "(" + s + ")";
		String s2 = "()" + s;
		String s3 = s + "()" ;
		
		if(!s1.equals(s2) && !s1.equals(s3)) {
			generateValidParanthesis(n-1, s1 );
		}
		if(!s2.equals(s3)) {
			generateValidParanthesis(n-1, s2);
		}
		
		generateValidParanthesis(n-1,  s3 );
		
	}

Haha,how about this bit-flipping solution
1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

Haha,how about this bit-flipping solution
1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

Another C++ version

#include <algorithm>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

/* Main Code Starts from here */

void bracketPermut(vector<vector<char> >& vii, vector<char>& vi, int l, int r, int n) {
    if(l>n)
        return;
    if(r == n) {
        vii.push_back(vi);
        return ;
    }
    else {
        if(l>r) {
            vi.push_back(')');
            bracketPermut(vii, vi, l, r+1, n);
            vi.pop_back();
        }
        vi.push_back('(');
        bracketPermut(vii, vi, l+1, r, n);
        vi.pop_back();
    }
}

vector< vector <char> > bracketPermut(int n) {
    vector <vector<char> > vii;
    vector<char> vi;
    bracketPermut(vii, vi, 0, 0, n);
    return vii;
}

int main() {

    vector< vector<char> > out = bracketPermut(5);
    for(auto i: out) {
        for(auto j:  i)
            cout << j << " ";
        cout<< endl;
    }
    return 0;
}

def gen(n, left=0, right=0,index=0,str=""):

    if index == 2*n:
        print(str)
        return

    if left < n:
        gen(n, left+1, right, index+1, str+"(")

    if right < left:
        gen(n, left, right+1, index+1, str+")")

def generateParenComb(left, right, left_stack, output):
    if right == 0:
				    print output
    if left > 0:
				    generateParenComb(left-1, right, left_stack+1, output+'(' )					
    if right>0 and left_stack>0:
				    generateParenComb(left, right-1, left_stack-1, output+')')
								
def topGenerateParenComb(num):
    generateParenComb(num, num, 0, "")				


topGenerateParenComb(4)

output:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

anyone knows the complexity?

ArrayList<String> pairs(int n){
	return pairs(n, n, "");
}
ArrayList<String> pairs(int open, int close, String s){
	ArrayList<String> ret = new ArrayList<String>();
	if(open == 0){
		for(int i = 0; i<close; i++){
			s += ")";
		}
		ret.add(s);
	} else{
		ret.addAll(pairs(open-1, close, s+"(");
		if(close > open){
			ret.addAll(pairs(open, close-1, s+")");
		}
	}
	return ret;
}

import unittest

def paren(n):
    if n == 0: yield ""
    for i in xrange(n):
        for j in paren(i):
            for k in paren(n - i - 1):
                yield j + "(" + k + ")"

def generate(n):
    print("Generating: 2 * {}".format(n))
    for s in paren(n):
        if len(s) == 2 * n:
            print(s)

class Test(unittest.TestCase):
    def test_generate(self):
        generate(0)
        generate(1)
        generate(2)
        generate(3)

if __name__ == "__main__":
    unittest.main()

public class ParanTest {
	public static void main(String[] args) {
		buildParan(new StringBuilder(), 0, 0, 3);
	}
	
	public static void buildParan(StringBuilder sb, int open, int close, int tot){
		if(close < open){
			StringBuilder newSb = new StringBuilder(sb.toString());
			newSb.append(')');
			int newClose = close;
			if(++newClose == tot){
				System.out.println(newSb.toString());
			}
			else{
				buildParan(newSb, open, newClose, tot);
			}
		}
		
		if(open < tot){
			int newOpen = open+1;
			sb.append('(');
			buildParan(sb, newOpen, close, tot);
		}
	}
}

public class AllBrackets {

    public static void main(String... a) throws Exception {
        printAll(Integer.parseInt(a[0]));
    }

    public static void printAll(int n) {
        printAll(new char[2 * n], 0, 0);
    }

    private static void printAll(char[] c, int index, int level) {
        if (index >= c.length) {
            System.out.println(new String(c));
            return;
        }
        if (level > 0) {
            c[index] = ')';
            printAll(c, index+1, level-1);
        }
        if (c.length - index > level) {
            c[index] = '(';
            printAll(c, index+1, level+1);
        }
    }
}

<?php

function printParanthesis(array $str,$index,$num,$open,$close)
{
if($open == $close && $open == $num)
{
echo implode("",$str)."\n";
return;
}

if($open < $num)
{
$str[$index]='(';
printParanthesis($str,$index+1,$num,$open+1,$close);
}

if($open > $close)
{
$str[$index]=')';
printParanthesis($str,$index+1,$num,$open,$close+1);
}
}

//main
$str = array();
$n = trim(fgets(STDIN));
printParanthesis($str,0,$n,0,0);

<?php

function printParanthesis(array $str,$index,$num,$open,$close)
{
    if($open == $close && $open == $num)
    {
        echo implode("",$str)."\n";
        return;
    }
   
    if($open < $num)
    {
        $str[$index]='(';
        printParanthesis($str,$index+1,$num,$open+1,$close);
    }
 
    if($open > $close)
    {
        $str[$index]=')';
        printParanthesis($str,$index+1,$num,$open,$close+1);
    } 
}

//main
$str = array();
$n = trim(fgets(STDIN));
printParanthesis($str,0,$n,0,0);

#include<iostream>

using namespace std;

void allPatterns(string str, int n, int open, int close){
        string str1, str2;
        str1 = str;
        str2 = str;
        if(n == 0){
                if((open - close) == 0)
                        cout<<str<<"\n";
                return;
        }
        else if((open - close) < 0)
                return;
        else{
                str1.append(1,'(');
                allPatterns(str1,--n,open+1,close);
                str2.append(1,')');
                allPatterns(str2,n,open,close+1);
        }
        return;
}

int main(){
        int open = 0, close = 0;
        string str;
        int n = 6;
        allPatterns(str,n,open,close);
}

The following algorithm uses the recursive formula to generate Catalan Numbers.

public class Catalan{
	public ArrayList< ArrayList< String> > allCatalanParentheses;

	public Catalan( int n ){
		for( int i = 0; i <= n; i ++ )
			allCatalanParentheses.add( new ArrayList<String>() );
		allCatalanParentheses.get( 0 ).add( "" );
	}

	public void generate( int n ){
		for( int k = 1; k < n; k ++ ){
			if( allCatalanParentheses.get( k ).size() == 0 ){
				generate( k-1 );
			}
			if( allCatalanParentheses.get( n - k ).size() == 0 ){
				generate( n - k );
			for( int i = 0; i < allCatalanParentheses.get( k-1 ).size(); i ++ ){
				for( int j = 0; j < allCatalanParentheses.get( n-k ).size(); j ++ ){
					allCatalanParentheses.get( n ).add( "(" + allCatalanParentheses.get( k-1 ).get( i ) + ")" + allCatalanParentheses.get( n-k ).get( j ) );
				}
			}
		}
	}

	public void print( int k ){
		for( int i = 0; i < allCatalanParentheses.get( k ).size(); i ++ )
			System.out.println( allCatalanParentheses.get( k ).get( i ) );
	}
}

This one uses grammar to generate

#include <iostream>
#include <list>
#include <string>
using namespace std;

list<string> allParens2n(int n)
{
    list<string> allParens(int n);

    return allParens(2*n);
}

//Direct implementation of B -> "" | B(B)
//Which is the unambiguous grammar of balanced parenthese
list<string> allParens(int n)
{
    list<string> returnValue;
    if(n == 0)
    {
        string s(""); 
        returnValue.push_back(s);
        return (returnValue);
    }
    
    for(int i = 0; i <= (n-2);i+= 2)
    {
        list<string> l = allParens(i);
        list<string> r = allParens(n-2-i);
        for(list<string>::iterator li = l.begin();li != l.end();li++)
            for(list<string>::iterator ri = r.begin();ri != r.end();ri++)
                {
                    string s("");
                    s+=*li;
                    s+="(";
                    s+=*ri;
                    s+=")";
                    returnValue.push_back(s);
                }
    }

    return returnValue;  
}
 
int main ()
{
    list<string> l = allParens2n(4);
    for(list<string>::iterator i = l.begin(); i != l.end();i++)
    {
        cout<<*i<<"\n";
    }
}

Ruby 2.0.0 implementation using a binary tree

OUTPUT = []
N=2

# creates a binary tree where left adds ( and right adds )
def search node
  # stop condition on the height of the tree
  if node.size >= 2*N
    # Add to valid output if it's valid
    OUTPUT << node if valid_answer node
    # return to father
    return node
  else
    # go left and go right adding the char
    left = search node+'('
    right = search node+')'
  end
end

# Verify if it's a valid leef
def valid_answer answer
  # temporary because we need to destroy the answer
  temp = answer.dup

  # keep closing parentesis
  while temp.include? "()"
    # remove closed parentesis
    temp.slice! "()"
  end

  # if there's no more char the all parentesis are valid
  if temp.size == 0
    return true
  else
    return false
  end
end

# Start tree
search ""

# output
puts OUTPUT

static void printAllParenthessis(int n, int openPar, int closePar, string currStr)
        {
            if (2 * n == currStr.Length)
            {
                Console.WriteLine(currStr);
            }
            if (openPar - closePar <= (2 * n - currStr.Length) / 2)
            {
                
                string newStr = currStr+"(";
                printAllParenthessis(n, openPar+1, closePar, newStr);
            }
            if (closePar < openPar)
            {
                string newStr = currStr + ")";
                printAllParenthessis(n, openPar, closePar + 1, newStr);
            }

        }

void Trace(std::vector<std::string> & rs, std::string cur, int left, int right, int n) {
  if (left == n) {
    cur.append(n - right, ')');
    rs.push_back(cur);
  } else {
    Trace(rs, cur + "(", left + 1, right, n);
    if (left > right) {
      Trace(rs, cur + ")", left, right + 1, n);
    }
  }
}

C++ Solution:

#include<iostream>
using namespace std;
int n;
void f(int o,int c,string t){
if(o==n && c==n){cout<<t<<"\n";}
else{
if(o+1<=n && o+1-c>=0){f(o+1,c,t+'(');}
if(c+1<=n && o-c-1>=0){f(o,c+1,t+')');}
}
}
int main(){
cin>>n;cout<<"\n\n";
string t;f(0,0,t);
}

However this is a recursive solution.. I'm wondering if we can use memorization to solve it for a better time complexity...

Python recursive implementation

def gen_valid_par(p, length, para_hist):
    if length < 0 or para_hist < 0:
        return -1
        
    if para_hist > length:
        return -1
        
    if length == 0 and para_hist == 0:
        print p
        return 1
        
    return gen_valid_par(p + '(', length - 1, para_hist + 1) + gen_valid_par(p + ')', length - 1, para_hist - 1)    


def main():
    n = int(raw_input())
    gen_valid_par("", 2*n, 0)


if __name__ == "__main__":
    main()

In the following
{...} means "a set of the elements ..."
where S = {...}, s is a string
S + s means the set of each of elements of S concatenated with s
s + S means the set of s concatenated with each of the elements of S
s1 + S + s2 means the s1 concatenated with each of the elements of S concatenated with s2

For n = 0 we have S0 == {}
For n = 1 we have S1 == {()}
For n > 1 we have Sk == {Sk-1 + (), () + Sk-1, ( + Sk-1 + )}

This is very easy to write in Scala as follows:

def parens(l:Int):Set[String] = {
  l match {
    case 0 => Set.empty
    case 1 => Set("()")
    case _ => (for (a <- parens(l-1)) yield Set("()" + a, a + "()", "(" + a + ")")).flatten
  }
}

To pretty print the results is similarly simply:

def pparens(l:int):Unit = parens (l) foreach println

For example:

scala> pparens(0)

scala> pparens(1)
()

scala> pparens(2)
()()
(())

scala> pparens(3)
(()())
((()))
()()()
(())()
()(())

scala> pparens(4)
(()()())
(()())()
((()()))
(()(()))
((()))()
(((())))
()(()())
()(())()
()((()))
()()(())
()()()()
(())()()
((())())

scala>

void print(int n) {
	vector<char> par(2 * n);
	int noOpen = 0, noClosed = 0;
	
	function<void(int)> back = [&](int k) {
		if(k == 2 * n) {
			for(int i = 0; i < par.size(); i++)
				cout << par[i];
			cout << endl;
		}
		else {

			if(noOpen - noClosed < 2 * n - k) {
				par[k] = '(';
				noOpen++;
				back(k + 1);
				noOpen--;
			}

			if(noClosed < noOpen) {
				par[k] = ')';
				noClosed++;
				back(k + 1);
				noClosed--;
			}
		}
	};

	back(0);
}

A simple c# implmentation

using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		int val = 3;
		char[] ch = new char[val * 2];
		PrintValidParanthesis(ch, val, val, 0);
	}
	
	public static void PrintValidParanthesis(char[] str, int left, int right, int count)
	{
		if (count == str.Length) { PrintParanthesis(str); return; }
		
		if (left != 0) 
		{
			str[count] = '(';
			PrintValidParanthesis(str, left - 1, right, count + 1);
		}
		
		if (left < right) 
		{
			str[count] = ')';
			PrintValidParanthesis(str, left, right - 1, count + 1);
		}
		
	}
	
	public static void PrintParanthesis(char[] str)
	{
		Console.WriteLine(str);
	}
}

Python

# number of left and right parenthesis not used yet
def foo(left,right):
    if left==0:
        temp = [')' for i in range(right)]
        return [''.join(temp)]
    
    if left==right:
        lst = foo(left-1,right)
        #what if lst == []
        return ['('+x for x in lst]
    else:
        lst1 = foo(left-1,right)
        
        lst2 = foo(left,right-1)
        l1= ['('+x for x in lst1]
        l2=[')'+x for x in lst2]
        return l1+l2
        
   


if __name__ == '__main__':
    for string in foo(3,3):
        print string

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

Set<String> genBrackets(int n) {
        if (n == 1) {
            return Collections.singleton("()");
        } else {
            Set<String> subs = genBrackets(n - 1);
            Set<String> retval = new HashSet<>();
            for (String s : subs) {
                retval.add("()" + s);
                retval.add("(" + s + ")");
            }

            return retval;
        }
    }

void GenerateValidParenthesis(std::string& s, int open, int close, int n)
{
    if (close == n)
    {
        std::cout << s << std::endl;
    }

    if (open > close)
    {
        GenerateValidParenthesis(s + ')', open, close + 1, n);
    }

    if (open < n)
    {
        GenerateValidParenthesis(s + '(', open + 1, close, n);
    }
}

def print_all_parenthesis(stack, history, iterations_left):
    
    if iterations_left == 0:
        if not stack:
            print(history)
    
    else:
        if not stack:        
            print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
        else:
            print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
            print_all_parenthesis(stack[:-1], history + ')', iterations_left - 1)
            

def wrapper(n):
    print_all_parenthesis([], '', n * 2)
    
wrapper(4)

A JavaScript solution

function _nParens(number){
    if(number < 1){
        return [];
    } 
    if(number === 1){
        return ["()"];
    }

    var holder = [];

    var prevParenthesis = nParens(number - 1);
    for(var i = 0; i < prevParenthesis.length; i++){
        var parenthesisAtIndex = prevParenthesis[i];

        for(var j = 0; j <= parenthesisAtIndex.length; j++){
            var left = parenthesisAtIndex.slice(0, j);
            var right = parenthesisAtIndex.slice(j, parenthesisAtIndex.length);
            holder.push(`${left}()${right}`);
        }
    }

    return holder;
}

function nParens(number){
    var res = _nParens(number);
    return Array.from(new Set(res))
}