22. Generate Parentheses

class Solution:
# time O(2^2) space O(N)
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        left = right = n
        s = ''
        def dfs(l,r,s,res):
            # early exit:
            if l > r:
                return 
            # base case:
            if l == 0 and r == 0:
                res.append(s)
            if l :
                dfs(l-1,r,s+'(',res)
            if r:
                dfs(l,r-1,s+')',res)
        dfs(left,right,s,res)
        return res 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        """
        # main idea: backtracking 
        """
        def btr(left,right,path): 
            # prevent cases ())( 
            if left > right:
                return 
            # update point 
            if left == 0 and right == 0:
                res.append(''.join(path))
                return
            if left > 0:
                left -= 1
                path.append('(')
                btr(left,right,path)
                path.pop()
                left += 1
            if right > 0:
                right -= 1
                path.append(')')
                btr(left,right,path)
                path.pop()
                right += 1 
        btr(n,n,[])
        return res