Q22-括号生成-中等-回溯法

22. 括号生成

Question

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

Example 1:

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

Example 2:

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

Note:

1 <= n <= 8

Approach 1: 暴力法

思路

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

算法

为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n-1 的序列前加一个 '(' 或 ')'。

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

class Solution:
    def generateParenthesis(self, n: int):
        def generate(A):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: # 合法字符串只可能出现差右括号的情况，不会差左括号
                    return False
            return bal == 0

        ans = []
        generate([])
        return ans

复杂度分析

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

Approach 2: 回溯法

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

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

class Solution:
    def generateParenthesis2(self, n: int):
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()

        backtrack([], 0, 0)
        return ans

复杂度分析

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

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

Approach 3: 按括号序列的长度递归

思路与算法

任何一个括号序列都一定是由 ( 开头，并且第一个 ( 一定有一个唯一与之对应的 )。这样一来，每一个括号序列可以用 (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) 函数返回之前，把返回值存储起来，下次再调用 generate(i) 时可以直接返回，不需要再递归计算。

class Solution:
    def generateParenthesis3(self, n: int):
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

复杂度分析

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