0022：括号生成（★）

2015-01-22 约 231 字预计阅读 1 分钟次阅读

力扣第 22 题

题目

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

分析

典型的回溯问题，每一步添加 ‘(’ 或 ‘)’，若无效则回到上一步。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(l,r,s):
            if r>l or l>n:
                return
            if r==n:
                res.append(s)
                return
            dfs(l+1,r,s+'(')
            dfs(l,r+1,s+')')
        res = []
        dfs(0,0,'')
        return res

时间 O(N)，41 ms

目录

0022：括号生成（★）

题目

分析

解答