Skip to content

Instantly share code, notes, and snippets.

@amarjitdhillon
Last active February 8, 2022 07:53
Show Gist options
  • Save amarjitdhillon/c4458a41a57d8f657d0630fb9d7d15ca to your computer and use it in GitHub Desktop.
Save amarjitdhillon/c4458a41a57d8f657d0630fb9d7d15ca to your computer and use it in GitHub Desktop.
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
open_count,close_count, result, r = 0, 0, [], []
def dfsParantheses(open_count,close_count,r):
if open_count == close_count == n: # base case, bottom of the tree
result.append("".join(r)) # add the parentheses list to the final result after converting it to string
return
if open_count < n : # as open brace can be added as long as it's count is less then what is allowed
r.append("(")
dfsParantheses(open_count+1,close_count,r)
r.pop() # to make it to the old state as we need to add ( again
if close_count < open_count: # closing brace can only be added if opening brace is there which means the count of closing brace will always be lesser then opening brace
r.append(")")
dfsParantheses(open_count,close_count+1,r)
r.pop()
dfsParantheses(0,0,r) # call recursive function
return result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment