lc022.括号生成

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
		
    def generateParenthesis3(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()

        backtrack([], 0, 0)
        return ans