Leetcode 78子集

22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

回溯需要画出树形图，能够发现其实原题能够转化为一个满二叉树

image-20240830183153460

但是根据情况肯定不能输出所有节点的值，所以需要一些剪枝。这里增加了left与right参数，分别代表左括号与右括号的数量，每生成一个就增加一个。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n <= 0:
            return []
        res = []

        def dfs(paths,left, right):
            if(left > n or right > left): return
            if len(paths) == n * 2:
                res.append(paths)
                return
            dfs(paths+'(', left + 1, right)
            dfs(paths+')', left, right + 1)
        dfs('',0,0)
        return res