mq050.括号生成

class Solution:
    def generateParenthesis1(self, n: int) -> List[str]:
        d = {
            "(": 1,
            ")": -1
        }

        def recursion(path, value):
            if len(path) == 2*n:
                if value == 0:
                    res.append("".join(path))
            else:
                if value > 0:
                    for e in "()":
                        path.append(e)
                        recursion(path, value+d[e])
                        path.pop()
                else:
                    path.append("(")
                    recursion(path, value+1)
                    path.pop()

        res = []
        recursion([], 0)
        return res
		
    @lru_cache(None)
    def generateParenthesis2(self, n: int) -> List[str]:
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans