22. 括号生成

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

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：
1 <= n <= 8

回溯算法

左右括号从 n 开始递减
剩余左括号总数要小于等于右括号

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def helper(result, left, right):
            if left == 0 and right == 0:
                ans.append(''.join(result))
                return
            if left == right:
                result.append('(')
                helper(result, left-1, right)
                result.pop()
            elif left < right:
                if left > 0:
                    result.append('(')
                    helper(result, left-1, right)
                    result.pop()
                result.append(')'),
                helper(result, left, right-1)
                result.pop()
        ans = []
        result = []
        helper(result, n, n)
        return ans