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 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.

## No comments:

## Post a Comment