Generate Parentheses, Leetcode 解题笔记

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:

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

又是一道DFS经典递归。对于这种问题我总是很混乱,因为涉及到递归时不像数组或是链表一样可以在纸上演示,大多数时候是一个空间迭代的过程,需要有一定的空间想象力。其实对于递归,只要把base case和递归操作想明白就行了。比如此题,其实就是当左括号数小于n时,可以增加左括号;当右括号数小于左括号数时,可以增加右括号。当左右括号数都等于n时(base case),把此string加入到最终结果中,并且返回上一级。

对于DFS和递归还是不熟练,还要多多练习。

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> ret = new ArrayList<String>();
        StringBuilder str = new StringBuilder();
        dfs(ret, str, 0, 0, n);
        return ret;
    }
    public void dfs(ArrayList<String> ret, StringBuilder str, int left, int right, int n){
        if(left == n && right == n){
            ret.add(str.toString());
            return;
        }
        if(left < n){
            str.append('(');
            dfs(ret, str, left+1, right, n);
            str.deleteCharAt(str.length()-1);
        }
        if(right < left){
            str.append(')');
            dfs(ret, str, left, right+1, n);
            str.deleteCharAt(str.length()-1);
        }
    }
}
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