class Solution:
  def generateValidParentheses(self, num):
   
    def backtrack(result, combo, left_count, right_count):
      
      if len(combo) == 2 * num:
        result.append(combo)
        return
      
      if left_count < num:
        backtrack(result, combo + '(', left_count + 1, right_count)
      
      if right_count < left_count:
        backtrack(result, combo + ')', left_count, right_count + 1)
    
    result = []
    backtrack(result, '', 0, 0)
    return result