https://leetcode.com/problems/generate-parentheses/ 描述 Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses. 给定n对括号，要求返回所有这些括号组成的不同的合法的字符串 For example, given n = 3, a solution set is: 输入：n = 3 "((()))" ,"(()())" ,"(())()" ,"()(())" ,"()()()"
题解 这道题目非常有意思，解法也很多，还是老规矩，我们先由易到难，先从最简单的方法开始入手。 我们来简单分析一下题目，n个括号对意味着字符串的长度是2n，我们利用排列组合可以计算出，所有的组合种数一共有 算一下会知道，这个数是很大的，也就是说我们哪怕一开始就知道答案，把答案遍历一遍也会有很高的耗时，所以这道题对于时间复杂度的要求应该不会很高。 暴力 能想到最简单的方法，当然是暴力，不要看不起这个朴素的算法，很多时候灵感都是从暴力当中获取的。 但是这道题暴力不太容易写，因为会有一种无从入手的感觉，我们知道要暴力，但是并不知道应该怎样暴力。 这道题不存在可以直接枚举的朴素元素，必须要我们拐个弯才行。 怎么拐弯呢，其实答案我刚才已经说出来了。 n个括号对，也就是说一共2n个字符，我们可以枚举n个'('分别放在什么位置，剩下的自然就是')'了。 看起来很有道理，但是有一个问题，就是这个思路并没有办法通过循环直接实现。 这其实已经进化成了一个搜索问题 了，我们要搜索所有可以摆放括号的可能性。 如果你能从暴力方法跳跃到搜索问题，那么说明你离写出代码已经很接近了。 如果不行，那么我建议你花点时间去学习一下搜索算法专题。 对于搜索问题而言，这已经很简单了，我们搜索的空间是明确的，2n个位置，搜索的内容，对于每个位置我们可以摆放'('也可以摆放')'。 那么代码自然而然呼之欲出： def dfs(pos, left , right , n, ret , cur_str):"" " po s: 当前枚举的位置t: 已经放置的左括号的数量t: 已经放置的右括号的数量t: 放置答案的数组"" " if pos == 2 *n:ret .append (cur_str)return if left < n:1 , left +1 , right , n, ret , cur_str+'(' )if right < n:1 , left , right +1 , n, ret , cur_str+')' )
这个程序遍历运行之后还没有结束，我们还需要判断生成出来的括号是否合法 ，也就是说括号需要匹配上。 我们可以用一个栈来判断括号是否能够匹配，比如我们遇见左括号就进栈，遇见右括号则判断栈顶，如果栈顶是左括号，那么栈顶的左括号出栈，否则则入栈，最后判断栈是否为空。 这个算法实现当然不难，但是如果你仔细去想了，你会发现完全没有必要用栈，因为如果我们遇到右括号的时候，栈顶不为左括号，那么一定最后是无法匹配的。 因为后面出现的左括号不能匹配前面出现的右括号，正所谓往者不可追 就是这个道理。 【狗头】 优化 我们来思考一个问题： 什么情况会出现右括号遇不到左括号呢？ 只有一种情况，就是当前出现右括号的个数超过了左括号，也就是说我们遍历一下字符串，如果中途出现右括号数量超过左括号的情况，那么就说明这个字符串是非法的。 看起来没毛病对吧，但是有问题，我们为什么不在枚举的时候就判断呢 ，如果左括号放入的数量已经等于右括号了，那么就不往里放置右括号，这样不就可以保证搜索到的一定是合法的字符串吗？ 如果你能想到这一层，说明你对搜索的理解已经很不错了。 我们看一下改动之后的代码： def dfs(pos, left , right , n, ret , cur_str):"" " po s: 当前枚举的位置t: 已经放置的左括号的数量t: 已经放置的右括号的数量t: 放置答案的数组"" " if pos == 2 *n:ret .append (cur_str)return if left < n:1 , left +1 , right , n, ret , cur_str+'(' )if right < n and right < left: 1 , left , right +1 , n, ret , cur_str+')' )
大部分代码都没有变化，只是在right < n后面加入了一个right < left这个条件。 看似只有一个条件，但是这个条件起到的作用至关重要。 整个算法的效率有了质的提升，实际上这也是效率最高的算法。 构造 上面的方案在LeetCode官方当中都有收入，也是比较常规的解法，下面要介绍的方法是我的原创，我个人感觉也比较有意思，分享给大家。 在之前的文章当中我们介绍过分治法，分治法的核心是将一个看似无法求解的大问题，分解成比较容易解决的小问题，最后加以解决。 这道题当中，我们直接求n时的解法是比较困难的，没办法直接获得，我们能不能也试着使用分治的方法来解决呢？ 我们来观察一下数据，当n=1的时候，很简单，结果是()，只有这一种。 当n=2呢？ 有两种，分别是(())和()()，当n=3呢？ 有5种： ((())), ()(()), ()()(), (()()), (())()。 这当中有没有规律呢？ 我们用solution(n)表示n对应的解法，那么我们可以写出solution(n)对应的公式： 上面这个式子有点像是动态规划的状态转移方程，虽然不完全一样，但是大概是那么回事。 也就是说我们可以用比答案规模小的答案组装成现在的答案 。 比如n=3时的答案，等于n=2时的答案和n=1时答案的拼接。 比如: solution(1) + solution(2) 可以得到： ()()()和()(())，solution(2) + solution(1)可以得到 ()()()和(())()。 但是还有一种答案无法通过拼接得到就是( solution(2) )。 也就是说在solution(2)的答案外面包一层括号。 那为什么不用考虑solution(1)的答案外面包两层括号呢？ 答案很简单，因为solution(2)已经包括了这样的情况，所以我们只用往下考虑一层。 不过还没有结束，还有一点小问题，就是这样得到的答案可能会有重复 ，所以我们需要去重，利用set我们可以很简单做到这点，让我们一起来看代码：
class Solution :def generateParenthesis (self, n: int) -> List[str]:# 记录下n=0和1时的答案 0 ] = set(["" ])1 ] = set(["()" ])# 遍历小于n的所有长度 for i in range(2 , n+1 ):# 遍历小于n的所有长度 for j in range(1 , i):# 构造答案 for s in ans1:for t in ans2:# 构造 ( solution(n-1) )这种答案 for s in solutionMap[i-1 ]:"(" + s + ")" )return list(solutionMap[n])
在C++当中，这两种方法的效率差不多，但是使用Python的话，构造的方法要更快一些。 和搜索这种方法相比，搜索是不知道答案去搜寻答案，而构造法是知道答案大概长什么样子，依据一定的规则生产答案 。 可以说是两种不同思路的解法，也是我本人很喜欢这道题的原因。 这道题的代码都不长，但是思路挺有意思，希望大家会喜欢。 今天的文章就是这些，如果觉得有所收获，请顺手点个在看或者转发 吧，你们的举手之劳对我来说很重要。 