22. 括号生成

佚名 5年前 (2019-05-12) 随笔 1188人围观抢沙发百度已收录

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

 1 public class GenerateParentheses {    
 2     //方法一：暴力法，直接使用递归生成所有的组合（包含重复的），
 3     public List<String> generateParenthesis1(int n) {
 4         List<String> res = new ArrayList<>();
 5         char[] str = new char[2 * n];
 6         generateAll(res, str, 0);
 7         return res;
 8     }
 9     
10     public void generateAll(List<String> res, char[] str, int pos) {
11         if(pos == str.length) {
12             if(check(str)) {
13                 res.add(new String(str));
14             }
15             return;
16         }
17         str[pos] = '(';
18         generateAll(res, str, pos+1);
19         str[pos] = ')';
20         generateAll(res, str, pos+1);        
21     }
22 
23     private boolean check(char[] str) {
24         int count = 0;
25         for(int i=0; i<str.length; i++) {
26             if(str[i] == '(') {
27                 count++;
28             }else {
29                 count--;
30             }
31             if(count < 0) {
32                 return false;
33             }
34         }
35         return count == 0;
36     }
37     
38     //方法二：回溯法
39     public List<String> generateParenthesis2(int n) {
40         List<String> list = new ArrayList<>();
41         generateValid(list, 0, 0, "", n);
42        return list;        
43     }
44     //只有一种括号类型，如果满足要求，则开括号数量始终大于等于闭括号，所以可以将许多不符合要求的递归提前抛弃
45     public void generateValid(List<String> list, int left, int right, String str, int n) {
46         System.out.println(str);
47         if (right > n-1) {
48             list.add(str);
49             return;
50         }
51         if (left < n) {
52             generateValid(list, left + 1, right, str + "(", n);
53         }
54         if (right < left) {
55             generateValid(list, left, right + 1, str + ")", n);
56         }        
57     }   
58     public static void main(String args[]) {
59         GenerateParentheses g = new GenerateParentheses();
60         g.generateParenthesis1(2);
61         g.generateParenthesis2(2);
62     }
63 }