LC 22括号生成Generate Parentheses　中等

给定整数 n，生成所有由 n 对左右括号组成、能够合法匹配的括号字符串。

思路 回溯计数剪枝：可放左括号当 left<n，可放右括号当 right<left，长度达 2n 收集。O(4^n/√n)。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans, path = [], []

        def dfs(left, right):
            if len(path) == 2 * n:
                ans.append("".join(path))
                return
            if left < n:
                path.append("(")
                dfs(left + 1, right)
                path.pop()
            if right < left:
                path.append(")")
                dfs(left, right + 1)
                path.pop()

        dfs(0, 0)
        return ans