# Can anyone explain the solution?

• 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)``````

• 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:
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.

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