Simple Recursive Python Solution


  • 1
    M

    This solution simplifies the recursive approach by starting with the number of right parens as 0 and then adding 1 to that number when a left paren is chosen. This way, an invalid path will never be chosen.

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        combos = []
        left = n
        right = 0
        path = ''
        self.formParen(left,right,path,combos)
        return combos
    
    def formParen(self,left,right,path,combos):
        if left == 0 and right == 0:
            combos.append(path)
        elif left == 0:
            combos.append(path+')'*right)
        elif right == 0:
            self.formParen(left-1,right+1,path+'(',combos)
        else:
            self.formParen(left-1,right+1,path+'(',combos)
            self.formParen(left,right-1,path+')',combos)

Log in to reply
 

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