What is the time complexity of the Generate Parentheses problem?

The time complexity is O(4^n / sqrt(n)), derived from Catalan numbers, representing the number of valid parentheses sequences for n pairs.

How does backtracking solve the Generate Parentheses problem?

Backtracking incrementally builds valid combinations of parentheses by adding open and close parentheses and ensuring the sequence is valid at each step.

What is state transition dynamic programming in the context of this problem?

State transition dynamic programming optimizes backtracking by caching intermediate results, reducing redundant calculations, and transitioning between valid states of parentheses.

How does pruning improve the backtracking solution for this problem?

Pruning avoids unnecessary recursive calls by stopping when a sequence exceeds valid parentheses constraints, thus improving the overall efficiency of the solution.

What are common pitfalls in solving the Generate Parentheses problem?

Common pitfalls include not properly balancing parentheses, failing to prune invalid sequences, and using inefficient solutions without dynamic programming or memoization.

#22

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例 1：输入： n = 3 输出： ["((()))","(()())","(())()","()(())","()()()"] 示例 2：输入： n = 1 输出： ["()"] 提示： 1

字符串动态规划回溯

题目描述

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

lightbulb

解题思路

方法一：DFS + 剪枝

题目中 $n$ 的范围为 $[1, 8]$ ，因此我们直接通过“暴力搜索 + 剪枝”的方式通过本题。

我们设计一个函数 $dfs(l, r, t)$ ，其中 $l$ 和 $r$ 分别表示左括号和右括号的数量，而 $t$ 表示当前的括号序列。那么我们可以得到如下的递归结构：

如果 $l \gt n$ 或者 $r \gt n$ 或者 $l \lt r$ ，那么当前括号组合 $t$ 不合法，直接返回；
如果 $l = n$ 且 $r = n$ ，那么当前括号组合 $t$ 合法，将其加入答案数组 ans 中，直接返回；
我们可以选择添加一个左括号，递归执行 dfs(l + 1, r, t + "(")；
我们也可以选择添加一个右括号，递归执行 dfs(l, r + 1, t + ")")。

时间复杂度 $O(2^{n\times 2} \times n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(l: int, r: int, t: str):
            if l > n or r > n or l < r:
                return
            if l == n and r == n:
                ans.append(t)
                return
            dfs(l + 1, r, t + "(")
            dfs(l, r + 1, t + ")")

        ans = []
        dfs(0, 0, "")
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to use backtracking for generating all combinations of valid parentheses?
question_mark
Can you explain how state transition dynamic programming can optimize the generation of valid parentheses combinations?
question_mark
Will you be able to discuss pruning techniques and their impact on performance when solving this problem?

warning

常见陷阱

外企场景

error
Failing to properly balance the number of opening and closing parentheses during backtracking leads to invalid sequences.
error
Not pruning invalid sequences early in the recursion can lead to unnecessary calls and performance issues.
error
Using an inefficient approach without dynamic programming or caching can result in excessive computation time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate Parentheses for k pairs instead of n.
arrow_right_alt
Generate Parentheses with additional constraints such as balanced and non-repeating sequences.
arrow_right_alt
Generate Parentheses but with nesting depth restrictions.

help

常见问题

外企场景

继续练习

#131 分割回文串 #140 单词拆分 II #691 贴纸拼词