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
{}{}
{{}}
{}
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(")");
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