Python DFS with explanation


  • 0
    S
    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            self.n = n
            self.res = []
            self.dfs(0, 0, [])
            return self.res
            
        def dfs(self, i, j, path):
            if i == self.n:
                while len(path) != self.n * 2:
                    path.append(")")
                self.res.append("".join(path))
                return
            self.dfs(i+1, j, path+["("])
            if j < i:
                self.dfs(i, j+1, path+[")"])
            return
    

    i is the count of "(" and j is the count of ")".

    The first character always has to be a opening parenthesis and then the next can either be another opening parenthesis or closing parenthesis depending on the following rules:

    • We cannot add a closing parenthesis if there are already the same amount of closing and opening parentheses
    • We can only add closing parentheses if i is equal to n

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.