leetcode 22 Generat Parentheses
z
 2018-03-12 21:04:24  

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:

1
2
3
4
5
6
7
8
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrace(0,0,"",n,ans);
        return ans;
    }
    public void backtrace(int left, int right, String s, int n, List<String> ans){
        if(s.length() == 2*n){
            ans.add(s);
            return ;
        }
        if(left < n)
            backtrace(left+1, right, s+"(", n, ans);
        if(right < left)
            backtrace(left, right+1, s+")", n, ans);
    }
}
  • Using backtrace method.
  • left means the number of ( , right means the number of ) . Each step, if left < n , this means that we should add ( to current string s , if right < left , this means that we should add ) to current string s.