题目

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

python解法

这道题用的是以前没遇到过的二叉树，太神奇了~~

以下思路来自于力扣题解：

这道题用到了二叉树的深度优先遍历思想。根据上图，我们发现： ①当左右括号的剩余个数均为0时，停止分支； ②产生左分支时，只需要查看是否还有剩余的左括号； ③而产生右分支的时候，除了查看是否剩余右括号以外，还需要查看右括号与左括号剩余数量的大小，以保证字符串中的左括号数量始终不小于右括号数量。

代码如下：

def generateParenthesis(self, n: int) -> List[str]: result = [] cur_str = "" def dfs(cur_str, left, right): """ :param cur_str: 从根结点到叶子结点的路径字符串 :param left: 左括号还可以使用的个数（剩余个数） :param right: 右括号还可以使用的个数 :return: None """ if left == 0 and right == 0: #左右括号剩余个数都为0，停止产生分支，result存放结果 result.append(cur_str) return if right < left: #如果右括号剩余个数小于左括号，说明字符串中右括号放多了，回退一步 return if left > 0: #先进行左分支 dfs(cur_str + '(', left - 1, right) if right > 0: #再进行右分支 dfs(cur_str + ')', left, right - 1) dfs(cur_str, n, n) return result