【LeetCode】22. 括号生成

题目

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

 

示例 1：

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

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

提示：

1 <= n <= 8

思路：

利用深度优先遍历，记录左括号可用个数left以及右括号可用个数right。

当left = right = 0的时候，则得到了一个正确答案

当left > right的时候，则剪枝，因为剩余的左括号比右括号多的时候，则后续无法组成合法的括号了

代码如下：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        # cur_str为当前的字符串
        cur_str = ''
        def dfs(cur_str, left, right):
            # left， right 为当前剩余的左右括号个数
            if left == 0 and right == 0:
                # 找到了满足条件的一个解，放入res中
                res.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 res