22.括号生成

思路：回溯，当左括号少于n时，可以继续加左括号；当右括号少于左括号时，可以继续加右括号。通过left和right分别表示当前左右括号的数量。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        #回溯法
        res = []
        def backtrack(s,left,right):
            if len(s) == 2*n:
                res.append(s)
                return 
            if left < n:
                backtrack(s+'(',left+1,right)
            if right < left:
                backtrack(s+')',left,right+1)
        backtrack('',0,0)
        return res