## Tuesday, January 29, 2013

### [leetcode] Generate Parentheses

Problem:
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)){
}
}
}
//add results of this number and go on.
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())
return result;
}

private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
if(number==1){
return;
}
StringBuilder sb = new StringBuilder();
for(String s:list.get(number-2)){
sb.append("(");
sb.append(s);
sb.append(")");
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){
return;
}
if(left<n)
generateParenthesis(s+"(",left+1,right,n);
if(right<left)
generateParenthesis(s+")",left,right+1,n);
}
}
```

Even More
There'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.