Sunday, September 7, 2014

Print all combinations of balanced parentheses

Reference Problem :- 
http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/

Problem Description :- 
Write a function to generate all possible n pairs of balanced parentheses.
For example, if n=1
{}
for n=2
{}{}
{{}}

My Approach 
For any number 'n' find all the ways in which n-1 parenthesis can be formed.
Now additional pair can be used in three ways 
1) Prefixing each with {}
2) Suffixing each with {}
3) Enclose each within {}
If 1) & 2) gives same result then we will take that combination just once.

Lets say that function returns list of combinations separated by semi-colon ;

Java implementation

import java.util.HashMap;
import java.util.Map;

class ParenthesesCombination {

public static void main(String[] args) {
for(int i=0;i<5;i++)
System.out.println("For n="+i+" "+printParanthesis(i));
}

// For simplicity I have used a static array to remember the result of previous calls.
public static Map<Integer, String>  resultMap = new HashMap<Integer, String>();

// Function returns patterns separated by semi-colon ;
public static String  printParanthesis(int n) {

if(resultMap.get(n)!= null ) return resultMap.get(n);
String  result=null;
if(n<1) result= "";
if (n==1) result= "{}";
if(n>1){
/* Find the way in which n-1 paranthesis can be formed.
Now two ways 1) Append it with  {}
2) Enclose it within {}
*/
String temp = printParanthesis(n-1);
// tokenize based on ;
String [] tempArr = temp.split(";");
for(String s:tempArr){
     String newPattern = s + "{}" +";" + "{"+s+"}"; // if s+"{}" looks different than "{}"+s then add that as well if(!(s+"{}").equals("{}"+s)) newPattern = newPattern +";"+ "{}"+s;
if(result==null){ result = newPattern; }else{ result = result +";"+newPattern; }  
}

}
resultMap.put(n,result);
return result;
}


}


Output :- 
For n=0 
For n=1 {}
For n=2 {}{};{{}}
For n=3 {}{}{};{{}{}};{{}}{};{{{}}};{}{{}}
For n=4 {}{}{}{};{{}{}{}};{{}{}}{};{{{}{}}};{}{{}{}};{{}}{}{};{{{}}{}};{}{{}}{};{{{}}}{};{{{{}}}};{}{{{}}};{}{{}}{};{{}{{}}};{}{}{{}}

No comments:

Post a Comment