22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

回溯

有点类似贪心，有左选左，不能选左的时候才选右。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>(); // 存储结果的列表
        backtrack(ans, new StringBuilder(), 0, 0, n); // 调用回溯函数生成括号组合
        return ans; // 返回结果列表
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        // 成功条件：当当前组合长度达到最大长度时，将其加入结果列表
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }

        // 失败条件隐藏在if里，即遇到失败条件就不会进入if。
        // 如果可以加左括号，即左括号数量小于最大值，继续添加左括号
        if (open < max) {
            cur.append('('); // 添加左括号
            backtrack(ans, cur, open + 1, close, max); // 递归调用，增加一个左括号
            cur.deleteCharAt(cur.length() - 1); // 撤销选择，回溯
        }
        // 如果可以加右括号，即右括号数量小于左括号数量，继续添加右括号
        if (close < open) {
            cur.append(')'); // 添加右括号
            backtrack(ans, cur, open, close + 1, max); // 递归调用，增加一个右括号
            cur.deleteCharAt(cur.length() - 1); // 撤销选择，回溯
        }
    }
}

• 时间复杂度： $O\left(\frac{4^n}{\sqrt{n}}\right)$ ，在回溯过程中，每个答案需要 $O(n)$ 的时间复制到答案数组中。
• 空间复杂度: $O(n)$ ，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 $O(1)$ 的空间，最多递归 $2 n$ 层，因此空间复杂度为 $O(n)$ 。

递归组合+备忘录。

generate函数，指定括号对数，生成所有可能的有效括号组合。对偶。假设括号里有3对括号，括号外就有n-4对括号。妙

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

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

• 我们需要枚举与第一个 '(' 对应的 ')' 的位置 $2i+1$ ；
• 递归调用 generate (i) 即可计算 $a$ 的所有可能性;
• 递归调用 generate $(n-i-1)$ 即可计算 $b$ 的所有可能性；
• 遍历 $a$ 与 $b$ 的所有可能性并拼接，即可得到所有长度为 $2 n$ 的括号序列。

为了节省计算时间，我们在每次 generate(i) 函数返回之前，把返回值存储起来，下次再调用 generate $(i)$ 时可以直接返回, 不需要再递归计算。

class Solution {
    // 缓存数组，用于存储中间结果，避免重复计算
    ArrayList[] cache = new ArrayList[100];

    public List<String> generate(int n) {
        // 如果缓存中已经有结果，直接返回缓存结果
        if (cache[n] != null) {
            return cache[n];
        }

        // 用于存储结果的列表
        ArrayList<String> ans = new ArrayList<String>();

        // 基本情况，当 n 为 0 时，返回一个空字符串
        if (n == 0) {
            ans.add("");
        } else {
            // 递归生成括号组合
            for (int c = 0; c < n; ++c) {
                // 生成左边的括号组合
                for (String left : generate(c)) {
                    // 生成右边的括号组合
                    for (String right : generate(n - 1 - c)) {
                        // 拼接左边和右边的括号组合，形成新的括号组合
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }

        // 将结果存入缓存
        cache[n] = ans;
        return ans; // 返回结果
    }

    public List<String> generateParenthesis(int n) {
        return generate(n); // 调用生成括号组合的方法
    }
}

• 时间复杂度： $O\left(\frac{4^n}{\sqrt{n}}\right)$。同方法一。
• 空间复杂度: $O\left(\frac{4^n}{\sqrt{n}}\right)$ ，此方法除答案数组外，中间过程中会存储与答案数组同样数量级的临时数组，是我们所需要的空间复杂度。