首页 > itarticle > leetcode 22 generat parentheses

leetcode 22 generat parentheses

admin 11月 14, 2020 0

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
 
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
class  {
    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.

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能