leetcode刷题指南之GenerateParentheses

题目分析

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

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

解题思路

算法：

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

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

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

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

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

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

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

算法正确性

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

举个例子

代码示例

作者：东大ACM退役队伍

编辑：刘凯旋