Backtracking, Python AC code


  • 0
    B
    class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        if n==0:
            return []
    
        # do it using backtracking
        result=[]
        def backtracking(right_num,left_num,temp,result):
    
            if right_num>n or left_num>n:
                return
    
            if right_num==left_num and right_num==n:
                result.append("".join(temp))
                return
    
            if left_num>right_num:
                return
    
            temp.append('(')
            backtracking(right_num+1,left_num,temp,result)
            temp.pop()
            temp.append(')')
            backtracking(right_num,left_num+1,temp,result)
            temp.pop()
    
        backtracking(0,0,[],result)
    
        return result
    

    what it does is a typical backtracking algorithm , every time try a binary choice (add "(" or ")")


Log in to reply
 

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