括号生成python

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

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

输入：n = 1
输出：["()"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 我们看图(借鉴他人的图)：

 这就是一个满二叉树。我们采用深度优先遍历将所有的可能都列表出来再筛选有效的括号。

def generateParenthesis(n: int):
    result = []
    # l,r分别是左括号和右括号的个数
    def dfs(s, l, r):
        if l > n or r > l:  # 当括号的个数超过n或者右括号的个数超过l就停止遍历
            return
        if len(s) == 2 * n:  # 括号是成对出现的所以乘2
            result.append(s)
            return
        dfs(s + '(', l + 1, r)  # 每遍历一个‘(’,l就加一
        dfs(s + ')', l, r + 1)  # 每遍历一个‘)’,r就加一

    dfs('', 0, 0)
    return result