22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        m = n * 2  # 括号长度
        ans = []
        path = [''] * m  # 所有括号长度都是一样的 m
        # open=左括号个数，i-open=右括号个数
        def dfs(i: int, open: int) -> None:
            if i == m:  # 括号构造完毕
                ans.append(''.join(path))  # 加入答案
                return
            if open < n:  # 可以填左括号
                path[i] = '('  # 直接覆盖
                dfs(i + 1, open + 1)  # 多了一个左括号
            if i - open < open:  # 可以填右括号
                path[i] = ')'  # 直接覆盖
                dfs(i + 1, open)
        dfs(0, 0)
        return ans