Leetcode打卡 | No.22 括号生成

No.22 括号生成

题目 ：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "()(())", "(())()", "()()()" ]

这一题和之前一题看起来类似 ，但难度却上升很多了 ，小伙伴们可以温故一下之前类似的题目 ：

Leetcode打卡 | No.20 有效的括号

两题差别有两个 ，一个是生成括号只包括小括号 ‘（）’ ，另一个是逻辑相逆 ，这里是要生成有效的括号序列 。一个很关键的问题就出来了 ，什么样的序列有效呢 ？当然可以参考第 20 题 ，但是这里更简单只有一种小括号字符 。分析发现只要左右小括号数量相等 ，生成的括号序列就有效 。

这里提供两种思路 ，一个是暴力法 ，生成所有的括号序列 ，再判断是否有效 ；一个是递归生成有效的序列方法 。

思路一 ：这里只有 ‘（ ’ 和 ‘ ）’ 两种字符可能 ，暴力生成所有字符串序列有 2的2n次方种可能 。根据自己的思维 ，小詹分成两个关键点讲解 ，一个是如何判断有效 ，一个是如何暴力生成所有字符串 。判断有效与否只需要当生成字符串序列长度为 2n 时判断是否左右括号数量相等 ；生成所有字符串则是利用递归思路 ，而只有左右括号两种可能 ，那么问题就简单了 ，见下代码 ：

思路二 ：与思路一不同 ，只有在我们知道序列仍然保持有效时才添加 '(' or ')' ，n 对括号意味着左右括号数量都为 n ，所以子函数可以以当前括号序列+左括号数量+右括号数量为参数 ，利用递归生成所有有效的括号序列 ！注意 ，这里生成的不在是所有的序列 ，而是通过控制左右括号数量生成有效序列 。具体代码如下 ：

而且提交表明 ，思路二的速度快很多 ，小詹提交第一次beat 93% ，第二次就哈哈哈 ，加鸡腿吧骚年们 。

原文发布时间为：2018-08-20本文作者：小詹同学本文来自云栖社区合作伙伴“ 小詹学Python”，了解相关信息可以关注“ 小詹学Python”。