括号

标签: 字符串 动态规划 回溯

难度: Medium

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

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

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

Submission

运行时间: 48 ms

内存: 15.1 MB

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        result = []

        def backtrack(path, stack):
            if len(path) == 2 * n and len(stack) == 0:
                result.append(''.join(path))
            
            if len(path) >= 2 * n:
                return

            if len(stack) == 0:
                choices = ['(']
            elif len(stack) == n:
                choices = [')']
            else:
                choices = ['(', ')']

            for choice in choices:
                if choice == '(':
                    stack.append(choice)
                else:
                    stack.pop()
                path.append(choice)
                backtrack(path, stack)
                path.pop()
                if choice == '(':
                    stack.pop()
                else:
                    stack.append(choice)

        backtrack([], [])
        return result

Explain

该题解使用回溯法来生成所有可能的合法括号组合。函数 `backtrack(path, stack)` 递归地构建括号串，其中 `path` 用于存储当前的括号组合，`stack` 用于模拟一个栈来确保括号的合法性（即，始终保持栈中的左括号数量不少于右括号）。递归终止条件是当 `path` 的长度达到 `2 * n` 且 `stack` 为空时，表示找到一个合法的组合。在递归过程中，基于当前 `stack` 的状态，选择添加 '(' 或 ')'。如果 `stack` 为空，只能添加 '('；如果 `stack` 的长度为 `n`（即已经添加了所有的左括号），只能添加 ')'；否则，既可以添加 '(' 也可以添加 ')'。每次添加后，递归调用 `backtrack` 继续构建路径，之后撤销该步骤（回溯），以尝试其他可能性。

时间复杂度: O(4^n / sqrt(n))

空间复杂度: O(n)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        result = []

        def backtrack(path, stack):
            # 检查是否形成了一个有效的序列
            if len(path) == 2 * n and len(stack) == 0:
                result.append(''.join(path))
            
            # 当路径长度达到最大时停止
            if len(path) >= 2 * n:
                return

            # 根据栈的状态决定下一步的选择
            if len(stack) == 0:
                choices = ['(']
            elif len(stack) == n:
                choices = [')']
            else:
                choices = ['(', ')']

            # 遍历选择，递归构建序列
            for choice in choices:
                if choice == '(':
                    stack.append(choice)
                else:
                    stack.pop()
                path.append(choice)
                backtrack(path, stack)
                path.pop()
                if choice == '(':
                    stack.pop()
                else:
                    stack.append(choice)

        backtrack([], [])
        return result

Explore

在回溯算法中，添加'('后立即在递归调用后将其从stack中移除是为了恢复到递归前的状态，这使得算法能够探索其它所有可能的括号组合。具体到这个场景，'('被添加到stack代表着一个未匹配的左括号，一旦通过递归尝试了这个选择后，需要将其从stack中移除以撤销这一操作，从而保证每次递归返回时，stack的状态都与进入当前递归层时一致，确保算法正确性。

是的，这个逻辑考虑了所有可能的括号添加顺序。在生成括号的问题中，任何时候添加的右括号数量都不能超过左括号数量。因此，如果stack的长度已经达到n，意味着所有n个左括号已经被添加到路径中，并且每个左括号都需要一个对应的右括号来匹配。此时，选择仅添加右括号')'是合理的，因为只有这样才能保证生成的括号字符串是有效的。

检查stack是否为空是为了确认所有添加的左括号都已被相应的右括号匹配。在生成括号的过程中，每个左括号'('都要求有一个对应的右括号')'来匹配，以确保括号字符串的有效性。如果在path长度达到2n时，stack不为空，意味着仍有未被匹配的左括号，这种情况下生成的括号组合是不完整且无效的。因此，终止条件同时包括path的长度和stack的状态是必要的。

在这个递归函数中，`path`代表当前构建中的括号字符串，是回溯算法中的'路径'，用于记录到目前为止所做的选择。`stack`代表了未匹配的左括号的计数，是用来保证括号匹配的辅助工具，不同于传统回溯算法中只有路径的概念。传统回溯通常涉及选择列表和路径，而这里的stack相当于是对路径有效性的实时检查工具。这种设计使得每次添加或回撤操作都能保证路径的合法性，即确保任何时刻路径中的右括号数不超过左括号数。