Tuesday, January 29, 2013

[leetcode] Generate Parentheses

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]+")"
             //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.
         //add the elements to list required by OJ.
         ArrayList<String> result = new ArrayList<String>();
         Iterator<String> it = list.get(list.size()-1).iterator();
         return result;
     private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
         StringBuilder sb = new StringBuilder();
         for(String s:list.get(number-2)){

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>();
        return list;
    private void generateParenthesis(String s,int left,int right,int n){
        if(left==n && right==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.

1 comment:

  1. They let you know that a $200 bet can be required to generate a $100 profit. Essentially, it means you'll earn 50% of your bet amount in profit. For example, a $200 bet would net you $100 in winnings, whereas a $40 bet at -200 코인카지노 would earn you a $20 profit. Sportsbooks provide a main point spread, puck line and run line. They either make things easier for you in exchange for a smaller potential payout or make things tougher in exchange for a larger potential payout. If the percentages begin with a plus (+), the numbers highlight the profit you'll earn by putting a $100 bet.