LeetCode 22：括号生成问题的 Python 回溯解法

题目描述

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

有效括号需满足：每个左括号 '(' 必须有对应的右括号 ')'；左右括号顺序必须合法（任意前缀中左括号数 ≥ 右括号数）。

示例

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

解题思路

本题适合使用回溯算法（DFS）解决。在构建括号字符串的过程中，我们需要维护两个计数器：已使用的左括号数量 left 和已使用的右括号数量 right。

为了保证生成的括号组合有效，需要遵循以下剪枝规则：

1. 如果 left < n，可以添加左括号 '('。
2. 如果 right < left，可以添加右括号 ')'。
3. 当 left == n 且 right == n 时，得到一个有效组合。

代码实现

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []

        def backtrack(current, left, right):
            if len(current) == n * 2:
                result.append(current)
                return
                
            if left < n:
                backtrack(current + '(', left + 1, right)
                
            if right < left:
                backtrack(current + ')', left, right + 1)

        backtrack("", 0, )
         result