Can anyone explain the solution?


  • 1

    My intuition told me the solution is correct, but if I think deeply into the solution, I have no idea why it does work.

    def generateParenthesis(self, n):
        res = []
        self.dfs(n, n, "", res)
        return res
    
    def dfs(self, leftRemain, rightRemain, path, res):
        if leftRemain > rightRemain or leftRemain < 0 or rightRemain < 0:
            return 
        if leftRemain == 0 and rightRemain == 0:
            res.append(path)
            return 
        self.dfs(leftRemain-1, rightRemain, path+"(", res)
        self.dfs(leftRemain, rightRemain-1, path+")", res)

  • 1
    T

    I guess the easiest is to check how it behaves on an input. First augment your code:

    def dfs(self, leftRemain, rightRemain, path, res):
        print "%s|-- %s %d to open, %d to close" % (len(path) * "|  ", path, leftRemain, rightRemain),
        if leftRemain > rightRemain or leftRemain < 0 or rightRemain < 0:
            print "-> bad:",
            if leftRemain > rightRemain: print "closed unopened"
            if leftRemain < 0: print "opened too many"
            if rightRemain < 0: print "closed too many"
            return 
        if leftRemain == 0 and rightRemain == 0:
            print "-> result"
            res.append(path)
            return
        print
        self.dfs(leftRemain-1, rightRemain, path+"(", res)
        self.dfs(leftRemain, rightRemain-1, path+")", res)
    

    Python print 101 for non-pyhtoners (like me):

    • print x will print x and put a newline
    • print will print nothing and put a newline
    • print x, will print x and put a space instead of a newline
    • string % (substitutionlist) is like printf(string, args)
    • num * string will repeat string num times

    Running this for n == 3 should give much insight as to how it works:

    |--  3 to open, 3 to close
    |  |-- ( 2 to open, 3 to close
    |  |  |-- (( 1 to open, 3 to close
    |  |  |  |-- ((( 0 to open, 3 to close
    |  |  |  |  |-- (((( -1 to open, 3 to close -> bad: opened too many
    |  |  |  |  |-- ((() 0 to open, 2 to close
    |  |  |  |  |  |-- ((()( -1 to open, 2 to close -> bad: opened too many
    |  |  |  |  |  |-- ((()) 0 to open, 1 to close
    |  |  |  |  |  |  |-- ((())( -1 to open, 1 to close -> bad: opened too many
    |  |  |  |  |  |  |-- ((())) 0 to open, 0 to close -> result
    |  |  |  |-- (() 1 to open, 2 to close
    |  |  |  |  |-- (()( 0 to open, 2 to close
    |  |  |  |  |  |-- (()(( -1 to open, 2 to close -> bad: opened too many
    |  |  |  |  |  |-- (()() 0 to open, 1 to close
    |  |  |  |  |  |  |-- (()()( -1 to open, 1 to close -> bad: opened too many
    |  |  |  |  |  |  |-- (()()) 0 to open, 0 to close -> result
    |  |  |  |  |-- (()) 1 to open, 1 to close
    |  |  |  |  |  |-- (())( 0 to open, 1 to close
    |  |  |  |  |  |  |-- (())(( -1 to open, 1 to close -> bad: opened too many
    |  |  |  |  |  |  |-- (())() 0 to open, 0 to close -> result
    |  |  |  |  |  |-- (())) 1 to open, 0 to close -> bad: closed unopened
    |  |  |-- () 2 to open, 2 to close
    |  |  |  |-- ()( 1 to open, 2 to close
    |  |  |  |  |-- ()(( 0 to open, 2 to close
    |  |  |  |  |  |-- ()((( -1 to open, 2 to close -> bad: opened too many
    |  |  |  |  |  |-- ()(() 0 to open, 1 to close
    |  |  |  |  |  |  |-- ()(()( -1 to open, 1 to close -> bad: opened too many
    |  |  |  |  |  |  |-- ()(()) 0 to open, 0 to close -> result
    |  |  |  |  |-- ()() 1 to open, 1 to close
    |  |  |  |  |  |-- ()()( 0 to open, 1 to close
    |  |  |  |  |  |  |-- ()()(( -1 to open, 1 to close -> bad: opened too many
    |  |  |  |  |  |  |-- ()()() 0 to open, 0 to close -> result
    |  |  |  |  |  |-- ()()) 1 to open, 0 to close -> bad: closed unopened
    |  |  |  |-- ()) 2 to open, 1 to close -> bad: closed unopened
    |  |-- ) 3 to open, 2 to close -> bad: closed unopened
    

    You can also see that or rightRemain < 0 is redundant.


Log in to reply
 

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