Leetcode–Generate Parentheses

The Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

Notes:

  1. I tried to derived the list of n from list of n-1, then found it’s not that easy! Try a different approach which is much simpler: Add a ‘(‘ if number of left not reach n, and add a ‘)’ if left more than right.

Java Solution

public class Solution {
    List<String> result;
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<String>();
        if(n==0)
            return result;
        gp(1, 1, n, "(");
        return result;
    }
    public void gp(int left, int lSubR, int n, String str){
        if(left==n && lSubR==0){// a valid string
            result.add(str);
        }
        else if(left==n){
            gp(left, lSubR-1, n, str+")");
        }
        else if(left < n){
            gp(left+1, lSubR+1, n, str+"(");
            if(lSubR > 0){
                gp(left, lSubR-1, n, str+")");
            }
        }    
    }
    
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s