括号生成[中等]

一、题目

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

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

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

1 <= n <= 8

二、代码

【1】暴力法： 我们可以生成所有2^2n个(和)字符构成的序列，然后我们检查每一个是否有效即可。为了生成所有序列，我们可以使用递归。长度为n的序列就是在长度为n?1的序列前加一个(或)。为了检查序列是否有效，我们遍历这个序列，并使用一个变量balance表示左括号的数量减去右括号的数量。如果在遍历过程中balance的值小于零，或者结束时balance的值不为零，那么该序列就是无效的，否则它是有效的。

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;
    }
}

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

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

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 (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);
        }
    }
}

我们的复杂度分析依赖于理解generateParenthesis(n)中有多少个元素。这个分析超出了本文的范畴，但事实证明这是第n个卡特兰数1/(n+1)(2n/n)，这是由4n/n渐近界定的。
时间复杂度： O(4n/n)，在回溯过程中，每个答案需要O(n)的时间复制到答案数组中。
空间复杂度： O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要O(1)的空间，最多递归2n层，因此空间复杂度为O(n)。

【3】按括号序列的长度递归： 任何一个括号序列都一定是由(开头，并且第一个(一定有一个唯一与之对应的)。这样一来，每一个括号序列可以用(a)b来表示，其中a与b分别是一个合法的括号序列（可以为空）。那么，要生成所有长度为2n的括号序列，我们定义一个函数generate(n)来返回所有可能的括号序列。那么在函数generate(n)的过程中：
1、我们需要枚举与第一个(对应的)的位置2i+1；
2、递归调用generate(i)即可计算a的所有可能性；
3、递归调用generate(n?i?1)即可计算b的所有可能性；
4、遍历a与b的所有可能性并拼接，即可得到所有长度为2n的括号序列。
为了节省计算时间，我们在每次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>();
        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(4^n/n)，该分析与方法二类似。
空间复杂度： O(4^n/n)，此方法除答案数组外，中间过程中会存储与答案数组同样数量级的临时数组，是我们所需要的空间复杂度。