Generate Parentheses

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:

“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路:
用open,close和pos三个变量来track生成合适的括号
1.如果open<n说明open括号还没有用完,可以在其后加一个open括号
2.如果close<open说明可以在其后加一个close的括号
3.如果pos和n*2相等,说明括号已经generate完成,结果加入result并return。

具体代码


public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String> ();
        if (n == 0)
            return result;
        return parenthesis(result, n, "", 0, 0, 0);
        
    }
    
    public ArrayList<String> parenthesis(ArrayList<String> result, int n, String in, int pos, int open, int close)
    {
        if (pos == n*2)
        {
            result.add(in);
            return result;
        }
        else
        {
            if (open < n)
            {
                String next = in + "(";
                parenthesis(result, n, next, pos+1, open + 1, close);
            }
            if (close < open)
            {
                String next = in + ")";
                parenthesis(result, n, next, pos+1, open, close + 1);
            }
            return result;
        }
        
    }
}

Second Submission: use left, right to keep track number of left and right parenthesis. if current left < n, then we can add one more (, if right < left, then we can add one ). Use recursion

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> result = new ArrayList<String> ();
        fillParenthesis(result, "", 0, 0, n);
        return result;
    }
    
    public void fillParenthesis (ArrayList<String> res, String curr, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(curr);
            return;
        }
        if (left < n) {
            String next = new String (curr);
            fillParenthesis(res, next + "(", left + 1, right, n);
        }
        if (right < left) {
            String next = new String(curr);
            fillParenthesis(res, next + ")", left, right + 1, n);
        }
    }
}

Follow up, if using different parentheses, (), [] and {}, how do you do it?

My thoughts: only thing is that you need to know what is the type of the open bracket, passing in a stack together with the used number of parenthesis can help solving this problem.

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