Advertisement
kai-rocket

Generate Parentheses

Mar 26th, 2021
775
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.96 KB | None | 0 0
  1. class Solution:
  2.     def generateParenthesis(self, n: int) -> List[str]:
  3.         # Invalid:
  4.         # more closing than opening
  5.         # num opening parens greater than n
  6.         valid_parens = []
  7.  
  8.         def find_valid_parens(curr_str, num_left, num_right):
  9.             # Check invalid
  10.             # If invalid, return to prune subtree
  11.             if num_right > num_left or num_left > n:
  12.                 return
  13.            
  14.             # Check valid
  15.             # If leaf node, add to valid_parens and return
  16.             if num_left == n and num_right == n:
  17.                 valid_parens.append(curr_str)    
  18.                 return
  19.            
  20.             # Recurse To keep going down tree
  21.             # Add left paren
  22.             find_valid_parens(curr_str + "(", num_left + 1, num_right)
  23.             # Add right paren
  24.             find_valid_parens(curr_str + ")", num_left, num_right + 1)
  25.  
  26.         find_valid_parens('', 0, 0)
  27.         return valid_parens
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement