leetcode刷题指南之GenerateParentheses

题目分析

给定n对圆括号,写一个函数生成所有的正确匹配的圆括号组合.

例子:给定 n = 3, 一个结果集如下

解题思路

算法:

题目要求使用回溯法进行求解.不了解回溯法的可以参考另一道题对回溯法思想的介绍.

简单观察一下本题的特征,发现

(1)每一个答案字符串的第一个圆括号都必须是左括号"(",所以第一个位置是不需要回溯的.

(2)另外,可以发现,其实对于给定的n,在每个答案字符串中左括号和右括号的数量都是n.并且在任意一个位置都有左括号的数量大于右括号的数量.

(3)根据前两条特性进行设计,很容易发现只要对每个位置满足第(2)条条件下,依次进行左右括号的遍历就可以了.

本题采用深度优先搜索的思想进行,每层对左右括号进行搜索,前提是满足上述的(1)(2)条件.

时间复杂度:最差情况是1/4C__,其中n表示n对圆括号,相当于在2n个位置中找到n个位置,前去不满足条件(1)的情况,为总数量的一半,并减去不满足第(2)个条件的情况,这个数量大约多于上一步求得的数量的一半.

算法正确性

正确性证明搜索过程等价于枚举.

举个例子

代码示例

作者:东大ACM退役队伍

编辑:刘凯旋

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181017B00Y0T00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券