LeetCode-Python-22. 括号生成

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

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

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

思路：

回溯+剪枝。

剪枝原则：

放了左括号才能放右括号，left 代表还能放左括号的个数，right 代表还能放右括号的个数。

class Solution(object):
    def generate(self, temp, left, right, result):
        if (left == 0 and right == 0):
            result.append(temp)
            return
        if (left > 0):
            self.generate(temp + "(", left - 1, right, result)
        if (left < right):
            self.generate(temp + ")", left, right - 1, result)
            
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.generate("", n, n, result)
        return result