def func_cache(func):
    saved = dict()

    def new_func(*para):
        if para in saved:
            return saved[para]
        else:
            ret = func(*para)
            saved[para] = ret
            return ret
    return new_func


class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        return self.parenthesis(n, n)

    @staticmethod
    @func_cache
    def parenthesis(l, r):
        if l < 0 or r <= 0:
            return ['']

        ret = []
        if l > 0:
            remain = Solution.parenthesis(l - 1, r)
            ret.extend(['(' + i for i in remain])
        if r > l:
            remain = Solution.parenthesis(l, r - 1)
            ret.extend([')' + i for i in remain])
        return ret
