p is the parenthesis-string built so far,
right tell the number of left and right parentheses still to add, and
parens collects the parentheses.
I used a few "tricks"... how many can you find? :-)
def generateParenthesis(self, n): def generate(p, left, right, parens=): if left: generate(p + '(', left-1, right) if right > left: generate(p + ')', left, right-1) if not right: parens += p, return parens return generate('', n, n)
Here I wrote an actual Python generator. I allow myself to put the
yield q at the end of the line because it's not that bad and because in "real life" I use Python 3 where I just say
yield from generate(...).
def generateParenthesis(self, n): def generate(p, left, right): if right >= left >= 0: if not right: yield p for q in generate(p + '(', left-1, right): yield q for q in generate(p + ')', left, right-1): yield q return list(generate('', n, n))
Improved version of this. Parameter
open tells the number of "already opened" parentheses, and I continue the recursion as long as I still have to open parentheses (
n > 0) and I haven't made a mistake yet (
open >= 0).
def generateParenthesis(self, n, open=0): if n > 0 <= open: return ['(' + p for p in self.generateParenthesis(n-1, open+1)] + \ [')' + p for p in self.generateParenthesis(n, open-1)] return [')' * open] * (not n)
I thought I know Python...
So, could you please tell me how could I get these advanced skills.
I learned a lot by reading tutorials/docs and by looking at solutions of others at checkio.org (a Python programming site) and by spending a month on Python topics at Stackoverflow. Also, practice practice practice :-)
Your program is very good, and I want to ask you some question. In solution 1, after line 3, the variable parens is not used as parameter of "generate(p + '(', left-1, right)", and why dose after this function the variable parens change?
@jh3 It's a default argument, so I don't have to explicitly provide it, and it's the same object for all calls. Here's some explanation that might help.
@erkangxu Makes it a tuple so it's equivalent to
I change your recursion solution 1 to make it even shorter.
I don't define another sub function.
By the way,
self.generateParenthesis is too long.
def generateParenthesis(self, n, left=0, right=0, cur=''): if left == n: return [cur + ')' * (n - right)] if left == right: return self.generateParenthesis(n, left + 1, right, cur + '(') return self.generateParenthesis(n, left + 1, right, cur + '(') \ + self.generateParenthesis(n, left, right + 1, cur + ')')
For solution 1:
I think the most import trick is that the default argument value is execute at define time, not runtime.
So, in this case, every changes to
parens in each recursive call, will change the same list, that's why the
parena will includes all the possible result.
Nice code! You are really familiar with python.
Haha, I actually use your every solution as the optimal solution to every problem on LC.
Thank you dude, for your good work!
@StefanPochmann Could you please explain how the third solution works? I can't figure it out...
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.