Leetcode——生成有效括号组合

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

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

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

思路：
1.递归的思路，也就是深度优先搜索DFS，假设一共有2n个格子，每一个格子都有两种搜索结果，所以时间复杂度是$2^{2n}$22n，就是全部都搜索出来了。
2.对上述方法做改进，在上述区间当中任意一个位置，左括号’(‘肯定要大于等于右括号不然就是无效的括号组合，’())'这样肯定是不行的对吧。

所以还是DFS，如果统计左括号的个数是小于n的，则加上’(‘就好了，然后再递归，如果左括号的数量大于右括号数量且右括号数量小于n，则加上’)'即可。

最后左右括号都不剩余的时候，也就是该排完的都排完了，最后得到result。

代码：

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.list = []
        self._gen(0, 0, n, "")
        return self.list
        
    def _gen(self, left, right, n, result):
        if left == n and right == n:    #一共就2n个括号，n对括号
            self.list.append(result)
            return
        if left < n:
            self._gen(left + 1, right, n, result + "(")
        if left > right and right < n:
            self._gen(left, right + 1, n, result + ")")