目录

0022:括号生成(★)

力扣第 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