Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example:
n=1: "()"
n=2: "()()","(())"
n=3: "((()))","()(())","()()()","(()())","(())()"
...
While this problem seems familiar to me, I didn't have good solutions at first glance. Then my first step was to observe more examples and tried to find some patterns.
Let [n] indicates all well-formed combinations of number n. Then it was not difficult to find out that we had the following patters:
[n] = { "(" + [n-1] + ")" , [1][n-1], [2][n-2], ...., [n-2][2], [n-1][1] }
where [m][n] indicates the cartesian product of two sets.
e.g. [2][2] = { "()()","(())" } x { "()()","(())" }
= { "()()()()","()()(())","(())()()","()()()()" }
As we can see, there will be duplicates of the product, so I use the Set container in java to avoid duplicates.
Then the main idea is to iterate from 1 to n. When calculate k, we can use the previous [1..k-1] results to generate the results of k.
public class GenerateParentheses {
public ArrayList<String> generateParenthesis(int n) {
ArrayList<Set<String>> list = new ArrayList<Set<String>>();
int number=1;
while (number<=n){
Set<String> parentheses = new HashSet();
//generate combinations of pattern "("+[number-1]+")"
generateParentheses(number,list,parentheses);
//generate combinations of pattern [1][number-1],[2][number-2],...[number-1][1]
for(int i=1;i<number;i++){
int leftIndex=i-1;
int rightIndex=number-i-1;
for(String left:list.get(leftIndex)){
for(String right:list.get(rightIndex)){
parentheses.add(left+right);
}
}
}
//add results of this number and go on.
list.add(parentheses);
number++;
}
//add the elements to list required by OJ.
ArrayList<String> result = new ArrayList<String>();
Iterator<String> it = list.get(list.size()-1).iterator();
while(it.hasNext())
result.add(it.next());
return result;
}
private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
if(number==1){
parentheses.add("()");
return;
}
StringBuilder sb = new StringBuilder();
for(String s:list.get(number-2)){
sb.append("(");
sb.append(s);
sb.append(")");
parentheses.add(sb.toString());
sb.setLength(0);
}
}
}
I know...The code looks messy and kind of crazy with 4-nested loops.
After surfing online and discussed with others, I have a much better solution with the idea that is much easier to illustrate.
When the parameter is n, we are going to have n left parenthesis and n right parenthesis. We can add either "(" or ")" to current constructed string (initially empty string), but with some constrains:
1. No. of left parenthesis "(" much be less or equal to n.
2. Certainly, right parenthesis ")" need to be <= n, but also need to be <= no. of "(".
Based this point, we can easily get a recursive approach :
public class GenerateParentheis {
ArrayList<String> list;
public ArrayList<String> generateParenthesis(int n) {
list = new ArrayList<String>();
generateParenthesis("",0,0,n);
return list;
}
private void generateParenthesis(String s,int left,int right,int n){
if(left==n && right==n){
list.add(s);
return;
}
if(left<n)
generateParenthesis(s+"(",left+1,right,n);
if(right<left)
generateParenthesis(s+")",left,right+1,n);
}
}
Even MoreThere're many problems that looks totally different at first glance, but are the same in nature.
The key in called Catalan Number. The n th Catalan number is 1/(n+1) * C(2n, n).
So when n=3, we can get Catalan number = 5, which is the total number of well-formed parenthesis combinations when n=3.
