class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        #TC: O(2^n)
        #SC: O(n)
        #simple combination problem

        res = []
        Set = set([])

        def dfs(S, left, right):
            if left < right:
                return

            if left > n:
                return

            if len(S) == 2*n:
                res.append(S)
                return

            dfs(S + '(', left + 1, right)
            dfs(S + ')', left, right+1)


        dfs('', 0, 0)
        return res