22. Generate Parentheses

Posted on | Edited on | Views:

LeetCode

Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<String> generateParenthesis(int n) {
        if(n==0) return new ArrayList<>();
        if(n==1) return new ArrayList<String>(Arrays.asList("()"));
        Set<String> set=new HashSet<String>();
        for(String str:generateParenthesis(n-1)){
            for(int i=0;i<str.length();i++){
                set.add(str.substring(0,i)+"()"+str.substring(i,str.length()));               
            }            
        }
        List<String> list = new ArrayList<String>(set);
        return list; 
    }
}
/* 
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans= new ArrayList();
        backtrack(ans,"",0,0,n);
        return ans;
    }
    public void backtrack(List<String> ans, String cur, int open,int close, int n){
        if(cur.length()==n*2){
            ans.add(cur);
            return;
        }
        if(open<n) backtrack(ans,cur+"(",open+1,close, n);
        if(close<open) backtrack(ans,cur+")",open,close+1,n);        
    }
}*/

link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
class Solution{
    public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<String>();
    generateOneByOne("", list, 0, 0, n);
    return list;
    }
    public void generateOneByOne(String sublist, List<String> list, int left, int right, int n){
        if(left < right){
            return;
        }
        if(left < n){
            generateOneByOne( sublist + "(" , list, left+1, right, n);
        }
        if(right < n){
            generateOneByOne( sublist + ")" , list, left, right+1, n);
        }
        if(left == n && right == n){
            list.add(sublist);
            return;
        }
    }
}*/

Explanation
Approach 3: Closure Number (DP)

First consider how to get the result f(n) from previous result f(0)…f(n-1).
Actually, the result f(n) will be put an extra () pair to f(n-1). Let the “(“ always at the first position, to produce a valid result, we can only put “)” in a way that there will be i pairs () inside the extra () and n - 1 - i pairs () outside the extra pair. link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int i = 0; i < n; ++i)
                for (String left: generateParenthesis(i))
                    for (String right: generateParenthesis(n-i-1))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

Time Complexity Analysis:

0%