2020-04-21 No.22 括号生成

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

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

题解：生成括号有两步，左括号少于n时加左括号，右括号少于左括号时加右括号

class Solution:
    def genPar(self, res, midStr, open, close, n):
        if len(midStr) == 2*n:
            res.append(midStr)
            return
        if open < n:
            self.genPar(res, midStr+'(', open+1, close, n)
        if close < open:
            self.genPar(res, midStr+')', open, close+1, n)

    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.genPar(res, '', 0, 0, n)
        return res