22. 括号生成

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

示例：

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

DFS+剪枝：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def fun(ans, s, l, r, n):
            if l>n or r>n or r>l:
                return
            if l==n and r==n:
                ans.append(s)
            fun(ans, s+'(', l+1, r, n)
            fun(ans, s+')', l, r+1, n)
            return
        fun(ans, "", 0, 0, n)
        return ans

回溯：

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