[NC]26. 括号生成

🚩传送门：牛客题目

题目

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

示例 1：

输入：n = 1 输出：[“()”]

示例 2：

输入：n = 2 输出：[“(())”,”()()”]

示例 3：

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

解法3： [“()丨(())“,”()丨()()“,”(())丨()”,”((()))丨”,”(()())丨”] ，第一个 ）的下标：1，3，5，符合 **2 × i + 1**

解题思路：暴力解

我们可以生成所有 个 ‘(‘ 和 ‘)’ 字符构成的序列，然后我们检查每一个是否有效即可。

n 对括号，故整个序列长度为 2n，对于每个位置无非两种，要么放置 ‘(‘ 要么放置 ‘)’

针对序列检查是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。

复杂度分析

时间复杂度：，其中 指的是括号对数。

  - 对于 ![](https://cdn.nlark.com/yuque/__latex/d46cf4a29e2964115eab6622e04a7c76.svg#card=math&code=2%5E%7B%5C%7B2n%5C%7D%7D&id=j0A37) 个序列中的每一个序列，我们用于建立和验证该序列的复杂度为 ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29%20&height=23&id=NO7Vv)

空间复杂度：，其中 指的是括号对数。

  - 除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 ![](https://cdn.nlark.com/yuque/__latex/2744619fca12271057dcb91f0e316d55.svg#card=math&code=%5Csmall%20O%281%29&height=23&id=XENFA) 的空间，最多递归 ![](https://cdn.nlark.com/yuque/__latex/2e75926f4f394e434567cc9bd91d351b.svg#card=math&code=%5Csmall%202n&id=zU9wO)  层（序列长度），因此空间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&height=23&id=SAGg2)。

官方代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    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;
    }
}

解题思路：回溯法

方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(‘ or ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点。

• 如果左括号数量不大于 n，我们可以放一个左括号。
• 如果右括号数量小于左括号的数量，我们可以放一个右括号。

复杂度分析

我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析超出了本文的范畴，但事实证明这是第 个卡特兰数 ，这是由 渐近界定的。

时间复杂度：，其中 指的是数组长度。

  - 在回溯过程中，每个答案需要  ![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&id=ybZvh)  的时间复制到答案数组中

空间复杂度：

  - 除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要  ![](https://cdn.nlark.com/yuque/__latex/5e079a28737d5dd019a3b8f6133ee55e.svg#card=math&code=O%281%29&id=nlwO8)  的空间，最多递归 ![](https://cdn.nlark.com/yuque/__latex/21e2c0c0472b331622877accbe29b91b.svg#card=math&code=2n&id=Cny8u) 层，因此空间复杂度为  ![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&id=ltuaq)  。

官方代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    // ans结果集、cur当前括号序列、open左括号个数、close右括号个数、n括号对数
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int n) {
        // 括号序列长度等于2n说明当前是一个完整合法序列
        if (cur.length() == n * 2) {
            ans.add(cur.toString());
            return;
        }
        // 左括号个数少于n个能添加
        if (open < n) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        // 当且仅当右括号个数小于左括号时,能添加头括号
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

解题思路：按括号序列的长度递归

规律找不出来，当场凉凉

任何一个括号序列都一定是由 **(** 开头，并且第一个 **(** 一定有一个唯一与之对应的 **)**。这样一来，每一个括号序列可以用 **(a)b** 来表示，其中 a 与 b 分别是一个合法的括号序列（可以为空）。

那么，要生成所有长度为 2 × n 的括号序列，我们定义一个函数 **generate(n)** 来返回所有可能的括号序列。那么在函数 generate(n) 的过程中：

• 我们需要枚举与第一个 **(** 所对应的括号 **)** 的位置 **2 × i + 1**；
• 递归调用 generate(i) 即可计算 a 的所有可能性；
• 递归调用 generate(n - i - 1) 即可计算 b 的所有可能性；
• 遍历 a 与 b 的所有可能性并拼接，即可得到所有长度为 2 × n 的括号序列。
• 为了节省计算时间，我们在每次 generate(i) 函数返回之前，把返回值存储起来，下次直接返回 。

复杂度分析

时间复杂度：，其中 指的是数组长度。

空间复杂度：

  - 此方法除答案数组外，中间过程中会存储与答案数组同样数量级的临时数组，是我们所需要的空间复杂度。

官方代码

class Solution {
    // 1. 缓存临时 generate(n) 括号对结果
    ArrayList[] cache = new ArrayList[100];
    public List<String> generate(int n) {
        // 2. 若缓存过结果直接返回
        if (cache[n] != null) {
            return cache[n];
        }
        // 3. 当前 n 的临时答案数组
        ArrayList<String> ans = new ArrayList<String>();
        // 4. 特殊情况 n=0 无括号对
        if (n == 0) {
            ans.add("");
        } 
        else {
            for (int i = 0; i < n; ++i) {
                // 5. 生产 a 部分的所有括号对
                for (String left: generate(i)) {
                    // 6. 生产 b 部分的所有括号对
                    for (String right: generate(n - 1 - i)) {
                        // 7. 拼接
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        // 8. 缓存
        cache[n] = ans;
        // 9. 返回临时结果
        return ans;
    }
    public List<String> generateParenthesis(int n) {
        return generate(n);
    }
}