Friday, August 26, 2016

GeeksForGeeks Print all combinations of balanced parentheses

Question reference
http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/
Write a function to generate all possible n pairs of balanced parentheses. 
For example, if n=1
{}
for n=2
{}{}
{{}}

I understood implementation from below  references
http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/
https://discuss.leetcode.com/topic/8724/easy-to-understand-java-backtracking-solution/2
Solution in Java
View point is that the no of "(" is equal to ")"


package generate_all_paranthesis;

import java.util.*;

public class Solution1 {
public ArrayList<String> generateParenthesis(int a
{
    ArrayList<String> res = new ArrayList<String>();
    if(a==0)
    {
    return res;
    }    
    backtracking(0,0,a,new StringBuilder(),res);
    return res;
}
public static void backtracking(int open,int close,int a,StringBuilder temp,ArrayList<String> res)
{
if(close==a)
{
res.add(temp.toString());
return;
}
else
{
           //go on adding ")" if open > close
if(open>close)
{
                                //appending ")"
                temp.append(")");
backtracking(open, close+1, a, temp, res);
temp.setLength(temp.length()-1);
                                //removing ")"

}
           //go on adding "(" if open <n
if(open<a)
{
                                //appending "("
                                temp.append("(");
backtracking(open+1, close, a, temp, res);
temp.setLength(temp.length()-1);
                                //removing "("
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
      Solution1 s1 = new Solution1();
      System.out.println(s1.generateParenthesis(3));
}

}





No comments:

Post a Comment