[leetcode] 22. 括号生成

题目描述

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

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

提示：

• 1 <= n <= 8

解题方法

方法一：dfs遍历

我说一下大体思路，我们设置dfs的左括号数为$left$，右括号数是$right$，$n$是括号对数，$str$是括号字符串，$list$是匹配的结果集。初始时$left$和$right$为0，$str$为空字符，$list$集合为空。每次dfs时$str$先匹配一个左括号，然后进入下一次dfs，等下一次dfs匹配完之后，$str$再匹配一个右括号，再进入下一次dfs。dfs的过程中可以通过剪枝去掉不匹配的括号组合，而当$str$是有效的括号组合时，则将$str$加入到$list$中，具体代码如下所示。

java代码

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    dfs(0, 0, n, "", result);
    return result;
}
//left左括号数，right右括号数，n是括号对数，str是括号字符串，list是匹配的结果集
public void dfs(int left, int right, int n, String str, List<String> list) {
    //右括号比左边的左括号多或者左括号超过了n个，则str字符串不是有效的括号组合
    if (right > left || left > n) {
        return;
    }
    //当左括号和右括号都是n时，有效的括号组合添加到结果集
    if (left == n && right == n) {
        list.add(str);
    }
    dfs(left + 1, right, n, str + '(', list);
    dfs(left, right + 1, n, str + ')', list);
}

dfs最大深度为n+1，n最高为8，所以不会栈溢出。

方法二：按照卡特兰数的思路递归求出有效括号组合

其实括号匹配的有效组合数符合卡特兰数，$n$是括号对数，$h(n)$是有效的括号数。

$h(n)={\sum }_{k=0}^{n-1}h(k)\ast h(n-1-k)$

我简单讲解一下为何会有这种关系。

假设有n对括号，我们设第一个左括号为A，与A对应的右括号为B。那么AB之间的括号，设有k对，那么B右侧的括号，就有n-1-k对。k的取值范围为0~n-1，对应n种情况。这n种情况的组合数相加，刚好为我上面提到的卡特兰数公式。

那么我们只需要按照卡特兰数递归的同时，求出从0~n，所有有效的括号结果集，即可得出n对括号的有效组合。

java代码

public List<String> generate(int n, List<String>[] cache) {
    if (cache[n] != null) {
        return cache[n];
    }
    ArrayList<String> ans = new ArrayList<>();
    if (n == 0) {
        ans.add("");
    } else {
        for (int k = 0; k < n; k++) {
            for (String left : generate(k, cache)) {
                for (String right : generate(n - 1 - k, cache)) {
                    //"("即为第一个左括号，")"即为第一个左括号对应的右括号，
                    // left即为k对括号中的一种有效组合，right即为n-1-k对括号中的一种有效组合
                    ans.add("(" + left + ")" + right);
                }
            }
        }
    }
    cache[n] = ans;
    return ans;
}

public List<String> generateParenthesis(int n) {
    List<String>[] cache = new ArrayList[n + 1];
    return generate(n, cache);
}

相似题目

[leetcode] 10. 正则表达式匹配
[leetcode] 17. 电话号码的字母组合