括号生成和判定的基本问题多基于回溯法解决

题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

示例

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

考察知识点

字符串、回溯算法、动态规划

核心思想

方法一：暴力法

思路

我们可以生成所有 \(2^{2n}\) 个 '(' 和 ')' 字符构成的序列（一共有n对括号，字符串长度为2n，每一位上可能出现的选择为2个，要么是’('，要么是‘)’，所以有\(2^{2n}\)个可能的序列）。然后，我们将检查每一个是否有效。

算法

为了生成所有序列，我们使用递归。长度为 n 的序列就是 '(' 加上所有长度为 n-1 的序列，以及 ')' 加上所有长度为 n-1 的序列。

为了检查序列是否为有效的，我们会跟踪平衡，也就是左括号的数量减去右括号的数量的净值。如果这个值始终小于零或者不以零结束，该序列就是无效的，否则它是有效的。

方法二：回溯法

思路和算法

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

如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。

有1组括号的组合方式，即"()"，

方法三：动态规划（官方题解的闭合数方法）

有2组括号时，新的组合方式为 "(())"或者"()()"，

有3组括号时，新的组合方式为 "((()))", "(()())", "(())()", "()(())", "()()()"

可以发现规律，我们考虑由i组括号组成的多个括号排列中的一个。考虑这个括号排列中最左边的括号，它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 "( )"，我们假设这一组括号是相比由 i-1 组括号组成的括号排列，而增加进来的新括号。

这个新加进来的括号，剩下的旧括号要么在这一组新增的括号内部"(())"->"((()))"，要么在这一组新增括号的外部（右侧）(())->(())()。

依赖i和i+1的关系，从i=0一直推导到i=n，即可得到n组括号的所有不重复组合方式。

既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：

"(" + 【i=p时所有括号的排列组合】 + ")" + 【i=q时所有括号的排列组合】

其中 p + q = n - 1，且 p q 均为非负整数。

事实上，当上述 p 从 0 取到 n-1，q 同时也从 n-1 取到 0 ，所有情况就遍历完了。

关于 p q 的解释，当 i=3 （即求解有3组括号时，新的组合方式）时，要遍历有0组括号、有1组括号、有2组括号三种情况，由于p + q = i -1 = 2 ，且 p 从 0 变到 i-1，q 同时也从 i-1 变到 0，所以有三种情况，分别是p=0,q=2/p=1,q=1/p=2,q=0，这三种情况下，已经有2组括号，再加上一组，就得到了有3组括号时，新的组合方式。

注：上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。

动态规划题解
LeetCode官方题解

Python版本

方法一暴力枚举法的实现

class Solution(object):
    def generateParenthesis(self, n):
        # 利用list做stack 本身list就有和stack类似的pop函数
        def generate(A = []):
            if len(A) == 2*n:  # 如果填充长度满足要求，就进行验证
                if valid(A):  # 验证该序列是否是有效的括号组合
                    ans.append("".join(A))
            else:
                # 关键在于如何枚举所有情况
                A.append('(')  
                generate(A)  # 先递归生成['(', '(', '(', '(', '(', '(']
                A.pop()  # 然后pop掉最后进来的一个括号，形成长度为 n-1 的序列。
                A.append(')')  # 最后再补上一个')'，这样一来，长度为6的序列上的每一位，都会出现'('和')'的情况。
                generate(A)
                A.pop()

        def valid(A):
            bal = 0  # 记录开括号（左括号）的数量
            for c in A:
                if c == '(': bal += 1  # 遇到开括号，bal加1。
                else: bal -= 1  # 遇到闭括号，bal减1。
                if bal < 0: return False  # 一旦发现bal小于0，说明序列开括号和闭括号不成对，闭括号多于开括号，返回
            return bal == 0  # bal != 0 and bal > 0 则说明开括号多于闭括号，返回False。否则说明，满足开闭括号成对且匹配，返回True。

        ans = []
        generate()
        return ans

    
print("leet code accept!!!")
Input = [3]
Input1 = [2]
Answer = [
    [
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()"
    ]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.generateParenthesis(Input[i])
        print(result)
        print(Answer[i])

复杂度分析
时间复杂度：\(O(2^{2n}n)\)，对于 \(2^{2n}\)个序列中的每一个，我们用于建立和验证该序列的复杂度为 \(O(n)\)。
空间复杂度：\(O(2^{2n}n)\)，简单地，每个序列都视作是有效的。请参见方法三以获得更严格的渐近界限。

方法二回溯法的实现

class Solution(object):
    def generateParenthesis(self, N):
        ans = []
        # S为选择路径 left和right为选择列表
        def backtrack(S = '', left = 0, right = 0):
            if len(S) == 2 * N:  # 结束条件为S的长度已经达到了2N
                ans.append(S)
                return  # 完成一次有效选择，返回上一层
            
            # 开始做选择
            if left < N:  # 如果left<N说明还可以放置开括号，就添加开括号，先添加开括号。 为什么要优先添加开括号，因为现有”(“后有”)“。
                backtrack(S+'(', left+1, right)  # backtrack(路径, 选择列表)
            
            # 添加完开括号之后，撤销选择。
            if right < left:  # 添加闭括号
                backtrack(S+')', left, right+1)  # 在原来S的基础上添加闭括号，相当于上面没有添加开括号，也就是把选择给撤销了。
        backtrack()
        return ans

我们的复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素。这个分析超出了本文的范畴，但事实证明这是第 n 个卡塔兰数 \(\dfrac{1}{n+1}\binom{2n}{n}\)，这是由 \(\dfrac{4^n}{n\sqrt{n}}\) 渐近界定的。 时间复杂度：\(O(\dfrac{4^n}{\sqrt{n}})\)，在回溯过程中，每个有效序列最多需要 n 步。 空间复杂度：\(O(\dfrac{4^n}{\sqrt{n}})\)，如上所述，并使用 \(O(n)\)O(n) 的空间来存储序列。

动态规划方法实现

class Solution5:
    def generateParenthesis(self, n: int) -> list:
        if n == 0:
            return []
        total_l = []
        total_l.append([None])    # 0组括号时记为None
        total_l.append(["()"])    # 1组括号只有一种情况
        for i in range(2,n+1):    # 开始计算i组括号时的括号组合
            l = []  # l这个list就是i组括号的所有情况
            for j in range(i):    # 开始求第i组括号，遍历0到i组括号的情况 p q ，其中p+q=i-1 , j 作为索引
                now_list1 = total_l[j]    # p = j 时的括号组合情况
                now_list2 = total_l[i-1-j]    # q = (i-1) - j 时的括号组合情况
                for k1 in now_list1:  # k1是第
                    for k2 in now_list2:
                        if k1 == None:
                            k1 = ""
                        if k2 == None:
                            k2 = ""
                        el = "(" + k1 + ")" + k2  # 这一行是关键
                        l.append(el)    # 把所有可能的情况添加到 l 中
            total_l.append(l)    # l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况
        return total_l[n]

另一个简洁的写法

'''
动态规划：
dp[i]表示i组括号的所有有效组合
dp[i] = "(dp[p]的所有有效组合)+【dp[q]的组合】"，其中 1 + p + q = i , p从0遍历到i-1, q则相应从i-1到0
'''
class Solution3:
    def generateParenthesis(self, n: int) -> list:
        dp = [[] for _ in range(n+1)]         # dp[i]存放i组括号的所有有效组合
        dp[0] = [""]                          # 初始化dp[0]
        for i in range(1, n+1):               # 计算dp[i]
            for p in range(i):                # 遍历p
                l1 = dp[p]                    # 得到dp[p]的所有有效组合
                l2 = dp[i-1-p]                # 得到dp[q]的所有有效组合
                for k1 in l1:
                    for k2 in l2:
                        dp[i].append("({0}){1}".format(k1, k2))

        return dp[n]

时间和空间复杂度：\(O(\dfrac{4^n}{\sqrt{n}})\)，该分析与 方法二 类似。