CareerCup

Why is ((())) not valid?

public static List<String> getCombinations(int n) {
	List<String> result = new ArrayList<String>();
	getCombinations(n, 0, "", result);
	return result;
}

public static void getCombinations(int available, int currentlyOpen, String prefix, List<String> acc) {
	// First possibility: add opening parenthesis (only if parentheses are still available)
	if (available > 0) {
		getCombinations(available-1, currentlyOpen+1, prefix + "(", acc);
	}
	// Second possibility: add closing parenthesis (only if at least one is open)
	if (currentlyOpen > 0) {
		getCombinations(available, currentlyOpen-1, prefix + ")", acc);
	}
	// If no parentheses are left and all of them are closed, we're done
	if (available == 0 && currentlyOpen == 0) {
		acc.add(prefix);
	}
}

public String parenthe(int n){
List<String>pr= new ArrayList<String>();
if(n==1){
return pr.add("()");
}
for(String s:parenthe(n-1)){
pr.add(s+"()");
pr.add("("+s+")");
if(s+"()"!="()"+s)
pr.add("()"+s);
}

public class Quiz {
String left = "(";
String right = ")";
static String output="";

public static void main(String[] args) {
Quiz quiz = new Quiz();
int number = 4;
quiz.parensSeperate(number);

if (number > 1){
output += ",";
quiz.parensConsis(number);
if(number > 2){
quiz.parensDiff(number, 1);
}
}
System.out.println(output);
}

private void parensDiff(int number, int i) {
if(number == (i+1)){
return;
}
output += ",";
parensConsis(number-i) ;
parensSeperate(i);

output += ",";
parensSeperate(i);
parensConsis(number-i) ;

parensDiff(number,i+1);
}

private void parensConsis(int i) {
for(int x=0;x<i;x++){
output += left;
}
for(int x=0;x<i;x++){
output += right;
}
}

private void parensSeperate(Integer i) {
if(i == null || i==0){
return;
}
output += left+right;
parensSeperate(i-1);
}

}

public class Quiz {
	String left = "(";
	String right = ")";
	static String output="";
	
	public static void main(String[] args) {
		Quiz quiz = new Quiz();
		int number = 4;
		quiz.parensSeperate(number);
		
		if (number > 1){
			output += ",";
			quiz.parensConsis(number);
			if(number > 2){
				quiz.parensDiff(number, 1);
			}
		}
		System.out.println(output);
	}
	
	private void parensDiff(int number, int i) {
		if(number == (i+1)){
			return;
		}
		output += ",";
		parensConsis(number-i) ;
		parensSeperate(i);
		
		output += ",";
		parensSeperate(i);
		parensConsis(number-i) ;
		
		parensDiff(number,i+1);
	}

	private void parensConsis(int i) {
		for(int x=0;x<i;x++){
			output += left;
		}
		for(int x=0;x<i;x++){
			output += right;
		}
	}

	private void parensSeperate(Integer i) {
		if(i == null || i==0){
			return;
		}
			output += left+right;
		parensSeperate(i-1);
	}

}

String left = "(";
String right = ")";
static String output="";

public static void main(String[] args) {
Quiz quiz = new Quiz();
int number = 4;
quiz.parensSeperate(number);

if (number > 1){
output += ",";
quiz.parensConsis(number);
if(number > 2){
quiz.parensDiff(number, 1);
}
}
System.out.println(output);
}

private void parensDiff(int number, int i) {
if(number == (i+1)){
return;
}
output += ",";
parensConsis(number-i) ;
parensSeperate(i);

output += ",";
parensSeperate(i);
parensConsis(number-i) ;

parensDiff(number,i+1);
}

private void parensConsis(int i) {
for(int x=0;x<i;x++){
output += left;
}
for(int x=0;x<i;x++){
output += right;
}
}

private void parensSeperate(Integer i) {
if(i == null || i==0){
return;
}
output += left+right;
parensSeperate(i-1);
}

for n=3, the output should be:
()()(), ()(()), (())(), (()()), ((()))

//Scala code

import scala.collection.mutable._

object BracketCombinations{

  def bracketCombinations(n: Int) = {
    def bracketCombinationsInternal(currN: Int,
                                    balanceStack: Stack[Char] = new Stack[Char],
                                    curr: String = "",
                                    acc: List[String] = Nil): List[String] =
    currN match {
      case 0 if balanceStack.isEmpty => acc:+curr

      case 0 if balanceStack.nonEmpty=>
                balanceStack.pop
                bracketCombinationsInternal(currN, balanceStack, curr+")", acc)

      case _ if balanceStack.isEmpty=>
                balanceStack.push('(')
                bracketCombinationsInternal(currN-1, balanceStack, curr+"(", acc)

      case _ if balanceStack.nonEmpty=>
                val newStack = new Stack[Char]
                balanceStack.foreach(newStack.push(_))
                newStack.push('(')
                balanceStack.pop
                bracketCombinationsInternal(currN-1, newStack, curr+"(", acc) ++
                bracketCombinationsInternal(currN, balanceStack, curr+")", acc)

     }
  bracketCombinationsInternal(n)
  }
}

void printBrackets(int n, int n_l, int n_r, string list){

if(n_l == n_r) {
if(n_l != n){
// only left bracket can be printed
list[n_l+n_r] = '(';
return printBrackets(n,n_l+1, n_r, list);
} else {
// print it
cout << list << endl;
return;
}
}
// if possible add '('
if(n_l < n){
list[n_l+n_r] = '(';
printBrackets(n,n_l+1, n_r, list);
}
list[n_l+n_r] = ')';
return printBrackets(n,n_l, n_r +1, list);
}

int main()
{
int numbers;
cin >> numbers;
string list(2*numbers,' ');
printBrackets(number,0,0,list);
return 0;
}

void printBrackets(int n, int n_l, int n_r, string list){
    
    if(n_l == n_r) {
        if(n_l != n){
            // only left bracket can be printed
            list[n_l+n_r] = '(';
            return printBrackets(n,n_l+1, n_r, list);
        } else {
            // print it
            cout << list << endl;
            return;
        }
    }
    // if possible add '('
    if(n_l < n){
        list[n_l+n_r] = '(';
        printBrackets(n,n_l+1, n_r, list);
    }
    list[n_l+n_r] = ')';
    return printBrackets(n,n_l, n_r +1, list);
}

int main(int argc, char **argv)
{
    int number;
    
    cin >> number;
    string list(2*number, ' ');
    printBrackets(number,0,0,list);
    return 0;
}