Q22 - Medium - 括号生成

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

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

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

回溯

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.back_track(0, 0, n, "", res)
        return res
        
    def back_track(self, l, r, n, temp, res):
        if l > n or r > n or l < r:
            return
        if l == n and r == n:
            res.append(temp)
            return
        self.back_track(l+1, r, n, temp+"(", res)
        self.back_track(l, r+1, n, temp+")", res)

    # def back_track(self, l, r, n, temp, res):
    #     if r == n:  # 右括号 = n，已满足，则记录
    #         res.append(temp)
    #     elif r == l:  # 左括号 = 右括号，且未满足，则只能添加左括号
    #         self.back_track(l+1, r, n, temp+"(", res)
    #     elif l > r:  # 左括号 > 右括号
    #         if l == n:  # 如果左括号已满而右括号未满，则只能添加右括号
    #             self.back_track(l, r+1, n, temp+")", res)
    #         elif l < n:  # 左括号未满且大于右括号，则添加两种都可以
    #             self.back_track(l+1, r, n, temp+"(", res)
    #             self.back_track(l, r+1, n, temp+")", res)