Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example,
i/p:
n = 3
o/p:
For example,
i/p:
n = 3
o/p:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
public class NewClass2 {
Set<String> br=new HashSet<String>();
void generate()
{
for(String i:br)
System.out.println(i);
}
void checkBalanced(String name)
{
HashMap<Character,Character> hm=new HashMap<Character,Character>();
hm.put('(',')');
Stack<Character> st=new Stack<Character>();
int c=0;
for(int i=0;i<name.length();i++)
{
if(hm.containsKey(name.charAt(i)))
{
st.push(name.charAt(i));
}else if(hm.containsValue(name.charAt(i)))
{
if(!st.empty() && hm.get(st.peek())==name.charAt(i))
{
st.pop();
}else
{c=1;
break;
}
}else
{
c=1;
break;
}
}
if(c==0 && st.empty())
br.add(name);
}
String swap(String s,int i,int j)
{
char c[]=s.toCharArray();
char t=c[i];
c[i]=c[j];
c[j]=t;
return String.valueOf(c);
}
void per(String s,int l,int r)
{
if(l==r)
checkBalanced(s);
for(int i=l;i<r;i++)
{
s=swap(s,l,i);
per(s,l+1,r);
s=swap(s,l,i);
}
}
public static void main(String args[])
{
int n=3;
String s="";
for(int i=0;i<n;i++)
{
s+="()";
}
NewClass2 ob=new NewClass2();
ob.per(s,0,s.length());
ob.generate();
}
}
No comments:
Post a Comment