Generate Parentheses (Difficulty: Medium)
- While this is a simple recursive solution, I would like to emphasize that we can use
yieldin Python to return multiple values with lazy manner. I believe this would be useful when a function is returning many values during its recursion.
class Solution:
def recursive_gen(self, current, opened, closed, n):
if opened == n and closed == n:
yield current
else:
if opened > closed: # can close the parentheses
yield from self.recursive_gen(current + ')', opened, closed + 1, n)
if opened + 1 <= n:
yield from self.recursive_gen(current + '(', opened + 1, closed, n)
def generateParenthesis(self, n: int) -> List[str]:
return list(self.recursive_gen('', 0, 0, n))