# 4-7 lines Python

• `p` is the parenthesis-string built so far, `left` and `right` tell the number of left and right parentheses still to add, and `parens` collects the parentheses.

Solution 1

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

Solution 2

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

Solution 3

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 :-)

• Thanks for your kind replying, I will keep learning with your advances.

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

• I am very grateful for your answer, and I have understood. Thank you very much!

• WOW,you are quite familiar with python! Nice solutions!

• abs fantastic, recursive and ifs together. you are the man, MAN!!!

• I notice the comma is needed in the first solution. Can you explain the trick there?

• @erkangxu Makes it a tuple so it's equivalent to `parens.append(p)`.

• what are the time and space complexity?

• This post is deleted!

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

• your response "practice,practice,practice'' give me hope, thanks

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

• I guess this is so called genius!

• I thought I knew python.
But this seems another python.
Genius!

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