class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        def insertParenthesis(res, s,n):
            # print("n:", n, "s:", s, "res:", res)
            if n < 1:
                res.add(s)
                return
            p = "()"
            m = len(s)//2
            for j in range(len(s)):
                insertParenthesis(res, s[:j] + p + s[j:],n-1)#pre and in insert
            insertParenthesis(res, s+p,n-1)# post insert
            
        res = set()
        s = ""
        insertParenthesis(res, s,n) 
        return [c for c in res]