1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 22. 括号生成

22. 括号生成

链接:https://leetcode-cn.com/problems/generate-parentheses/
难度:中等

题目

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

示例:

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

思路

这道题DFS可以解决,具体有多少种解法大家可以去看下题解。一题多解,面试不愁。

方案代码

解决方案:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur_str = ''

        def dfs(cur_str, left, right):
            if left == 0 and right == 0:
                res.append(cur_str)
                return
            if right < left:
                return
            if left > 0:
                dfs(cur_str + '(', left - 1, right)
            if right > 0:
                dfs(cur_str + ')', left, right - 1)

        dfs(cur_str, n, n)
        return res

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/317.html