22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入输出

1
2
3
4
5
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

基本思路

  1. 暴力解法 递归的生成所有可能的情况 一共有$2^n$种 接着利用valid()判断是否符合 方法是实时监测左括号数量减右括号数量的值 若该值小于0 或者最后不等于0 则不符合情况 时复$O(2^{2n})$ 空复$O(n)$

  2. 深搜

    1. 函数dfs(int n, int lc, int rc, String str)

      n-括号对数 lc-左括号数量 rc-右括号数量 str-当前维护的字符串序列

    2. 有以下三种情况：

      1. if(lc == n && rc == n) 序列合法 直接加入result
      2. if(lc < n) 左括号数量小于n 则在str后拼接左括号
      3. if(rc < lc < n) 右括号数量小于左括号 则在str后拼接右括号

java实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 暴力
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        generateAll(new char[2*n], 0, result);
        return result;
    }

    public void generateAll(char[] current, int pos, List<String> result) {
        if(pos == current.length){
            if(valid(current)){
                result.add(new String(current));
            }
        }
        else{
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    public boolean valid(char[] current){
        int balance = 0;
        for(char c : current){
            if(c == '('){
                balance++;
            }else{
                balance--;
            }
            if(balance < 0){
                return false;
            }
        }
        return balance == 0;
    }
}

// 深搜
class Solution {
    List<String> result = new ArrayList<String>();
    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return result;
    }

    public void dfs(int n, int lc, int rc, String str){
        if(lc == n && rc == n){
            result.add(str);
        }
        else{
            if(lc < n) dfs(n, lc+1, rc, str+"(");
            if(rc < n && lc > rc) dfs(n, lc, rc+1, str+")");

        }
    }
}