0022 括号生成

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(l: int, r: int, t: str):
            if l > n or r > n or l < r:
                return
            if l == n and r == n:
                ans.append(t)
                return
            dfs(l + 1, r, t + "(")
            dfs(l, r + 1, t + ")")

        ans = []
        dfs(0, 0, "")
        return ans

if __name__ == "__main__":
    sol = Solution()
    print(sol.generateParenthesis(3))  # ["((()))","(()())","(())()","()(())","()()()"]
    print(sol.generateParenthesis(1))  # ["()"]