题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路

回溯，正确的括号匹配方式是
左括号的个数一定要大于当前右括号的数目。

class Solution:
    def generateParenthesis(self, n):
        res = []
        def helper(temp, left, right):
            if len(temp) == n * 2:
                res.append(temp)
                return 
            if left < n:
                helper(temp + "(", left + 1, right)
            if right < left:
                helper(temp + ")", left, right + 1)
        helper("", 0, 0)
        return res