Leetcode Hot 100 括号生成 - 小宇の万事屋

701 words

4 minutes

Leetcode Hot 100 括号生成

2026-04-10

Algorithm

Leetcode

/

Hot 100

/

回溯

/

剪枝

/

字符串

/

算法

Leetcode Hot 100 继续推进，这题轮到回溯家族里的经典节目：括号生成。

这题的关键，不是把所有括号串都列出来再挨个验尸，而是：

在生成的过程中，就别让非法前缀活着走到下一层。

也就是说，这题不是纯暴力，而是带着规则意识的回溯剪枝。

一句话先定调：

边生成，边约束，边剪枝。

这就是它最有味道的地方。

题目链接#

LeetCode 22. 括号生成

题目描述#

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

括号生成题目截图

解题思路：回溯 + 合法性约束#

如果只看表面，这题像是在长度为 2n 的字符串里，每一位都填：

(
)

但如果真这么干，就会产生大量垃圾串。比如：

1
)))(((
2
())())

这些字符串要么一开头就崩了，要么中途就已经非法，根本没必要让它们活着走完整个递归树。

所以更聪明的思路是：

在回溯过程中，始终保证当前前缀合法。

这样搜出来的每一条路径，都是有希望成为答案的正经选手。

合法括号串的两个核心限制#

假设当前已经放了：

left 个左括号 (
right 个右括号 )

那么递归过程中必须一直满足两个条件。

1. 左括号数量不能超过 `n`#

因为总共就只有 n 个左括号配额。

也就是说，只有当：

1
left < n

时，才能继续放左括号。

2. 右括号数量不能超过左括号数量#

这是这题真正的灵魂约束。

如果某个时刻出现：

1
right > left

说明右括号已经提前把左括号“关穿了”，当前前缀立刻非法。

因此，只有当：

1
right < left

时，才允许继续放右括号。

可以粗暴记成一句：

左括号别超额，右括号别抢跑。

代码实现#

1
class Solution(object):
2
    def generateParenthesis(self, n):
3
        """
4
        :type n: int
5
        :rtype: List[str]
6
        """
7
        ans = []
8
        vals = []
9

10
        def dfs(left, right):
11
            if len(vals) == 2 * n:
12
                ans.append(''.join(vals))
13
                return
14

15
            if left < n:
16
                vals.append('(')
17
                dfs(left + 1, right)
18
                vals.pop()
19

20
            if right < left:
21
                vals.append(')')
22
                dfs(left, right + 1)
23
                vals.pop()
24

25
        dfs(0, 0)
26
        return ans