leetcode-generate-parentheses

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/generate-parentheses/

　　生成所有n个左括号和n个右括号的合法的组合

题目分析

　　经典的深度优先搜索或者说回溯法。

代码

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
31
32
33
34
public class Solution {
    
    private Character[] path;
    private List<String> ans;
    
    public void search(int idx, int left, int right, int n) {
         if (idx >= 2 * n) {
             StringBuilder sb = new StringBuilder();
             for (int i = 0; i < 2 * n; i++) {
                 sb.append(path[i]);
             }
             ans.add(sb.toString());
             return;
         }
         if (left > 0) {
             path[idx] = '(';
             search(idx + 1, left - 1, right, n);
             if (left < right) {
                 path[idx] = ')';
                 search(idx + 1, left, right - 1, n);
             }
         } else {
             path[idx] = ')';
             search(idx + 1, left, right - 1, n);
         }
    }
    
    public List<String> generateParenthesis(int n) {
        path = new Character[2 * n];
        ans = new ArrayList<String>();
        search(0, n, n, n);
        return ans;
    }
}