Write a function, Brackets(n), where n is an integer, which will print all valid pairings of parenthesis. For example, Brackets(3) should print
()()()
(())()
()(())
(()())
((()))
Try not to use brute force and generate 2^n combinations.
My solution to the above question in JAVA is
package solved200;
import java.util.Stack;
public class Brackets {
private final int n;
String open = "(";
String close = ")";
String[] tokens = new String[]{open, close};
int count;
public Brackets(int n) {
this.n = 2*n;
mainStack = new Stack
}
public void printBrackets(){
printBracketsHelper(this.n, 0, 0);
}
private void printBracketsHelper(int k, int numCloseBrackets, int numOpenBrackets){
if(k == 0){
if( numOpenBrackets == numCloseBrackets) {
count++;
printStack();
}
return;
}
for(int i = 0; i < tokens.length; i++){ boolean addToStack = false; String curToken = tokens[i]; if(mainStack.size() == 0) { if( curToken.equals(close)) { push(curToken); numCloseBrackets++; addToStack = true; } } else { if( curToken.equals(open)){ if( numOpenBrackets + 1 <= numCloseBrackets) { push(curToken); numOpenBrackets++; addToStack = true; } } else if( curToken.equals(close)){ if( numOpenBrackets <= numCloseBrackets + 1) { push(curToken); numCloseBrackets++; addToStack = true; } } } if( addToStack ) { printBracketsHelper(k-1, numCloseBrackets, numOpenBrackets); String popStr = mainStack.pop(); if( popStr.equals(close)) numCloseBrackets--; else if (popStr.equals(open)) numOpenBrackets--; } } } private String push(String curToken) { // System.out.println("PUSH " + curToken); return mainStack.push(curToken); } private void printStack() { System.out.print(count + ": "); for(int i = mainStack.size() - 1; i>=0; i--){
System.out.print(mainStack.get(i));
}
System.out.println();
}
public static void main(String[] args) {
Brackets b = new Brackets(15);
b.printBrackets();
System.out.println("Total : " + b.count);
}
}
