数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解法：使用回溯控制生成的左右，使用left和right记录生成的括号数量，每次进行回溯时，判断当前的括号情况，满足条件：

• 先生成左括号（，再生成右括号）
  -如果左括号少于n，就递归的生成左括号，如果右括号少于左括号，就生成右括号，因为每次生成都会判断，所以可以满足闭合性

左右括号天然的分成2部分，所以会分开考虑左右括号，咋一看很容易没有思路

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n==0:
            return []
        ans=[]
        def backtrace(path,left,right):
            if len(path)==2*n:
                ans.append(''.join(path))
                return
            if left<n:
                path.append('(')
                backtrace(path,left+1,right)
                path.pop()
            if right<left:
                path.append(')')
                backtrace(path,left,right+1)
                path.pop()
        backtrace([],0,0)
        return ans