Generate Parentheses

LeetCode 22

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.res = []
        self.dfs(n, n, "")
        return self.res   
        """
        破題為:左右括號數同 代入 DFS 
                 (
                /  \
               (    ) 
              / \  / \      
             (   )(   ) <-- right < left return None
              \  / ...
               ) (
                \ \
                 ) )
                  \ \
                   ) )
        """
    def dfs(self, left, right, path):
        if right < left:
            return
        if left == 0 and right == 0:
            self.res.append(path)
        if left>=0:
            self.dfs(left-1, right, path+"(")
        if right>=0:
            self.dfs(left, right-1, path+")")