首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

LeetCode 22 [Generate Parentheses]

LeetCode 22 [Generate Parentheses]

原题

    给定 n 对括号,请写一个函数以将其生成新的括号组合,并返回所有组合结果。

样例
给定 n = 3, 可生成的组合如下:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路

    求所有的组合,递归, backtracking
    left,right分别代表左括号和右括号还剩几个 - 规则就是:任何时候剩余的右括号都要大于等于左括号
    当left和right都等于零的时候,向result中添加一个可行解

完整代码

    class Solution(object):
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
            res = []
            if n < 1:
                return res
            self.helper(n, n, "", res)
            return res
            
        def helper(self, left, right, path, res):
            if left > right:
                return
            if left == 0 and right == 0:
                res.append(path)
            if left > 0:
                self.helper(left - 1, right, path + "(", res)
            if right > 0:
                self.helper(left, right - 1, path + ")", res)
返回列表