Generate Parentheses

Leave a comment

May 14, 2017 by oneOokay

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 + Backtracking:但是难点在于,我怎么知道是否是valid的,什么时候加左括号,什么时候加右括号?

这个DFS的方法就在于,在generating string的是时候只产生valid的,这样就不用担心到最后判定这个string是不是valid .

用了两个int,一个表示左括号数目,一个表示右括号数目,根据这两个数目的大小与N的大小来决定下一层DFS的时候,是继续加左括号还是加油括号.

另外还有一个DP的解法,目前不是很想看…

public List generateParenthesis(int n) {
        List ans = new ArrayList<>();
        if (n <= 0) return ans;
        helper(0, 0, "", ans, n);
        return ans;
    }
    
    private void helper(int open, int close, String str, List ans, int n){
        if (open == n && close == n){
            ans.add(new String(str));
            return;
        }
//当左括号的数目小于总的N的时候,还可以继续加左括号.        
        if (open < n){             
helper(open + 1, close, str + '(', ans, n);
         }
//同时也是可以加右括号的,所以这里不是else if而是if
         if (open > close){
            helper(open, close + 1, str + ')', ans, n);
        }
    }
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

%d bloggers like this: