专栏首页Petrichor的专栏leetcode: 22. Generate Parentheses

leetcode: 22. Generate Parentheses

Problem

# Given n pairs of parentheses, 
# write a function to generate all combinations of well-formed parentheses.
#
# For example, given n = 3, a solution set is:
#
# [
#   "((()))",
#   "(()())",
#   "(())()",
#   "()(())",
#   "()()()"
# ]

Idea

l_num = 剩余的 左括号数
r_num = 剩余的 右括号数

只需要保证 l_num <= r_num ,当前的组合就一定是有效的。

AC

class Solution():
    def generateParenthesis(self, n):
        res = []
        self.generate(res, '', n, n)
        return res
    def generate(self, res, cur, l_num, r_num):
        if l_num <= r_num:
            if r_num == 0:
                res.append(cur)
                return
            if l_num > 0:
                self.generate(res, cur+'(', l_num-1, r_num)
            if r_num > 0:
                self.generate(res, cur+')', l_num, r_num-1)


if __name__ == "__main__":
    assert Solution().generateParenthesis(3) == ['((()))', '(()())', '(())()', '()(())', '()()()']

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 77. Combinations

    Petrichor_
  • 【python】快排的三种实现

    Petrichor_
  • leetcode: 74. Search a 2D Matrix

    Petrichor_
  • 【leetcode】12:整数转罗马数字

    例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II ...

    帅地
  • 【leetcode刷题】T193-各位相加

    https://leetcode-cn.com/problems/add-digits/

    木又AI帮
  • 【每天一道编程系列-2018.2.11】(Ans)[补]

    The number of daffodils refers to an n-digit number (n≥3), the sum of the n-th ...

    yesr
  • acm-大数问题集锦

    大数问题,其实就是模拟运算,因为系统自带的int long bouble这些类型无法容纳百位千位的大数字,从而手动模拟运算过程,使用字符串来表示这样的超大数字,...

    十四君
  • 【leetcode刷题】T176-移掉K位数字

    https://leetcode-cn.com/problems/remove-k-digits

    木又AI帮
  • 献给前端求职路上的你们(下)

    真正面试中,面试官往往采用的是由难到易的套路,那js和jQuery就是重中之重了,以及针对项目和所用技术方面的一些问题也就是你的必备储粮啦! JavaScrip...

    用户1667431
  • 空间金字塔池化(Spatial Pyramid Pooling, SPP)原理和代码实现(Pytorch)

    想直接看公式的可跳至第三节 3.公式修正 一、为什么需要SPP 首先需要知道为什么会需要SPP。 我们都知道卷积神经网络(CNN)由卷积层和全连接层组成,其中...

    marsggbo

扫码关注云+社区

领取腾讯云代金券