题目描述

题目链接

https://leetcode.cn/problems/generate-parentheses/

思路

1. 暴力法

我们可以生成所有个和字符构成的序列，然后我们检查每一个是否有效即可。为了生成所有的括号序列，我们可以使用递归，长度为的序列就是在长度为的序列前加一个或。

如何判断一个括号序列合法？实际上，一个合法的括号序列需要满足两个条件：

• 左右括号数量相等。
• 任意前缀中左括号数量 >= 右括号数量，也就是说每一个右括号总能找到相匹配的左括号。

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

public static List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    recur(new char[2 * n], 0, res);
    return res;
}
private static void recur(char[] str, int index, List<String> res) {
    if (index == str.length) {
        if (valid(str)) {
            res.add(new String(str));
        }
        return;
    }
    str[index] = '(';
    recur(str, index + 1, res);
    str[index] = ')';
    recur(str, index + 1, res);
}
private static boolean valid(char[] str) {
    int balance = 0;
    for (char c: str) {
        if (c == '(') {
            ++balance;
        } else {
            --balance;
        }
        // 一旦右括号数量大于左括号数量，则括号无效
        if (balance < 0) {
            return false;
        }
    }
    return balance == 0;
}

• 时间复杂度：，对于个序列中的每一个，我们用于建立和验证该序列的复杂度为。
• 空间复杂度：，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要的空间，最多递归层，因此空间复杂度为。

  2. 回溯法

  方法一还有改进的余地：我们可以只在序列仍然保持有效时才继续添加或，而不是像方法一那样每次都添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，如果左括号数量不大于，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

以为例画图展示：

代码实现：

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    // open为左括号数量、close为右括号数量
    recur(new StringBuilder(), 0, 0, n, res);
    return res;
}
private void recur(StringBuilder sb, int open, int close, int max, List<String> res) {
    if (open == max && close == max) {
        res.add(sb.toString());
        return;
    }
    // 先递归全是左括号的情况
    if (open < max) {
        sb.append("(");
        recur(sb, open + 1, close, max, res);
        // 回溯
        sb.deleteCharAt(sb.length() - 1);
    }
    // 如果右括号数量小于左括号的数量，我们可以放一个右括号
    if (close < open) {
        sb.append(")");
        recur(sb, open, close + 1, max, res);
        // 回溯
        sb.deleteCharAt(sb.length() - 1);
    }
}

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

• 时间复杂度：，在回溯过程中，每个答案需要的时间复制到答案数组中。
• 空间复杂度：，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要的空间，最多递归层，因此空间复杂度为。

  3. 按括号序列的长度递归

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

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

• 我们需要枚举与第一个对应的的位置；
• 递归调用即可计算的所有可能性；
• 递归调用即可计算的所有可能性；
• 遍历与的所有可能性并拼接，即可得到所有长度为的括号序列。

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

public List<String> generateParenthesis(int n) {
    return generate(n);
}
private final Map<Integer, ArrayList<String>> cache = new HashMap<>();
public List<String> generate(int n) {
    if (cache.get(n) != null) {
        return cache.get(n);
    }
    ArrayList<String> ans = new ArrayList<>();
    if (n == 0) {
        ans.add("");
    } else {
        for (int c = 0; c < n; ++c) {
            // 计算所有a的可能性
            for (String left: generate(c)) {
                // 计算所有b的可能性
                for (String right: generate(n - c - 1)) {
                    ans.add("(" + left + ")" + right);
                }
            }
        }
    }
    cache.put(n, ans);
    return ans;
}

• 时间复杂度：，该分析与方法二类似。
• 空间复杂度：，除答案数组外，中间过程中会存储与答案数组同样数量级的临时数组。