1. 题目描述（中等难度）

给一个数字 n ，返回所有合法的括号匹配，刚好和20题相反。 自己没想出来，全部参考 LeetCode 给出的 Solution。

解法一 暴力破解

列举所有的情况，每一位有左括号和右括号两种情况，总共 2n 位，所以总共 种情况。 1. public List generateParenthesis(int n) { 2. List combinations = new ArrayList(); 3. generateAll(new char[2 * n], 0, combinations); 4. return combinations; 5. } 6. 7. public void generateAll(char[] current, int pos, List result) { 8. if (pos == current.length) { 9. if (valid(current)) 10. result.add(new String(current)); 11. } else { 12. current[pos] = '('; 13. generateAll(current, pos+1, result); 14. current[pos] = ')'; 15. generateAll(current, pos+1, result); 16. } 17. } 18. 19. public boolean valid(char[] current) { 20. int balance = 0; 21. for (char c: current) { 22. if (c == '(') balance++; 23. else balance--; 24. if (balance < 0) return false; 25. } 26. return (balance == 0); 27. }

时间复杂度：对每种情况判断是否合法需要 O（n），所以时间复杂度是 。 空间复杂度： ，乘以 n 是因为每个串的长度是 2n。此外这是假设所有情况都符合的时候，但其实不可能都符合，后边会给出更精确的情况。

解法二

解法一中，我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。 还有一种情况就是如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。因为每个右括号必须和之前的某个左括号匹配，如果右括号数量多于左括号，那么一定有一个右括号没有与之匹配的左括号，后边不论加多少左括号都没有用了。例如 n = 3 ，总共会有 6 个括号，我们加到 ( ) ) 3 个括号的情况的时候，有 1 个左括号，2 个右括号，此时后边 3 个括号无论是什么，已经注定它不会是合法序列了。 基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。 1. public List generateParenthesis(int n) { 2. List ans = new ArrayList(); 3. backtrack(ans, "", 0, 0, n); 4. return ans; 5. } 6. 7. public void backtrack(List ans, String cur, int left, int right, int n){ 8. if (cur.length() == n * 2) { 9. ans.add(cur); 10. return; 11. } 12. //左括号不要超过 n 13. if (left < n) 14. backtrack(ans, cur+"(", left+1, right, n); 15. //右括号不要超过左括号 16. if (right < left) 17. backtrack(ans, cur+")", left, right+1, n); 18. }

时间复杂度： 空间复杂度： 递归的复杂度分析，继续留坑 =.=。

解法三

解法二中是用列举的方法，仔细想想，我们每次用递归的时候，都是把大问题换成小问题然后去解决，这道题有没有这个思路呢？ 我们想一下之前的列举过程，第 0 个位置一定会是左括号，然后接着添加左括号或右括号，过程中左括号数一定大于或等于右括号数，当第一次出现左括号数等于右括号数的时候，假如此时的位置是 c 。那么位置 1 到 c - 1 之间一定是合法序列，此外 c + 1 到最后的 2n -1 也是合法序列。而假设总共是 n 组括号，1 到 c - 1 是 a 组括号， c + 1 到 2n - 1 之间则是 n - 1 - a 组括号，如下图 最重要的是，每一个合法序列都会有这么一个数 c ，且唯一。所以我们如果要求 n 组括号的所有序列，只需要知道 a 组括号以及 ( n - a - 1) 组括号的所有序列，然后两两组合即可。 以 n = 3 为例，我们把 0 到 c 之间的括号数记为 a 组， c + 1 到最后的括号数记为 b 组，则 a = 0，b = 2 对应 （）（（））以及 （）（）（） 两种情况，此时 c = 1。 a = 1，b = 1，对应 （（））（（）） 一种情况，此时 c = 3。 a = 2，b = 0 对应 （（（）））， （（）（）） 两种情况，此时 c = 5。 所以我们如果要想求 n 组括号，只需要知道 a 组和 b 组的情况，然后组合起来就可以了。 看起来我们在迭代 a ，其实本质上是在迭代 c ，c = 2a + 1，迭代 a 从 0 到 n - 1 ，就是迭代 c 从 1 到 2n - 1。看起来 c 都是奇数，其实是可以理解的，因为 0 到 c 间都是一组组的括号， 所以 c 一定是奇数。为什么可以迭代 c ，因为上边说到每一个合法序列都对应着一个 c ，遍历 c 的话，就能得到所有的情况了，看一下代码吧。 1. public List generateParenthesis(int n) { 2. List ans = new ArrayList(); 3. if (n == 0) { 4. ans.add(""); 5. } else { 6. for (int a = 0; a < n; a++) 7. for (String left: generateParenthesis(a)) 8. for (String right: generateParenthesis(n-1-a)) 9. ans.add("(" + left + ")" + right); 10. } 11. return ans; 12. }

时间复杂度： 空间复杂度： 留坑。

扩展 卡塔兰数

如果这道题不是让你列举所有的情况， 而是仅仅让你输出 n 对应下有多少种合法序列，该怎么做呢？ 答案就是 ，也可以写成 。怎么证明呢？我主要参考了这里，说一下。 我们假设不考虑是不是合法序列，那么就一共有 种情况，然后我们只需要把里边的非法情况减去就可以了，一共有多少种非法情况呢？ 首先我们用 就保证了一定是有 n 个左括号，n 个右括号，那么为什么出现了非法序列？ 为了方便论述，我们把左括号记为 +1，右括号记为 -1. ps：下边的 和 都是指两个数的和，不是你和我中的和。 我们假设非法序列的集合是 M ，而非法序列就是列举过程中右括号数比左括号数多了，也就是和小于 0 了，变成 -1 了。这种情况一旦出现，后边无论是什么括号都改变不了它是非法序列的命了。我们将第一次和等于 -1 的时候的位置记为 d 。每一个非法序列一定存在这样一个 d 。然后关键的地方到了！ 此时我们把 0 到 d 所有的 -1 变成 1，1 变成 -1，我们将每一个非法序列都这样做，就构成了一个新的集合 N ，并且这个集合 N 一定和 M 中的元素一一对应（ N -> M，在集合 N 中第一次出现和为 1 的位置也就是 d ，把 0 到 d 中所有的 -1 变成 1，1 变成 -1 就回到了 M），从而集合 M 的数量就等于集合 N 的数量。集合 N 的数量是多少呢？ 我们来分析下集合 N 是什么样的，集合 N 对应的集合 M 原来的序列本来是这样的，在 0 到 d 之间和是 -1 ，也就是 -1 比 +1 多一个，d + 1 到最后的和一定是 1（因为 n 个 +1 和 n 个 -1 的和一定是 0 ，由于 0 到 d 和是 -1，后边的和一定是 1），也就意味着 +1 比 -1 多一个。而在集合 N 中，我们把 0 到 d 的 -1 变成了 +1 ，+1 变成了 -1 ，所以也变成了 +1 比 -1 多一个，所以集合 N 总共就是 +1 比 -1 多 2 个的集合，也就是 n + 1 个 +1 和 n - 1 个 -1 。 所以集合 N 就是 2n 个位置中选 n - 1 个位置放 -1，其他位置放 +1，总共就有 ，所以集合 M 也有 种。 所有合法序列就有 。 将集合 M 和集合 N 建立了一一映射，从而解决了问题，神奇！！！！！！！！！！其实，这个数列就是卡塔兰数，可以看下维基百科的定义。 而这个数列，其实除了括号匹配，还有很多类似的问题，其本质是一样的，例如， 2n 个人排队买票，其中 n 个人持 50 元，n 个人持 100 元。每张票 50 元，且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序，不至于使售票处找不开钱？ 对于一个无限大的栈，一共n个元素，请问有几种合法的入栈出栈形式？ P = a1 a2 a3 … an，其中 ai 是矩阵。根据乘法结合律，不改变矩阵的相互顺序，只用括号表示成对的乘积，试问一共有几种括号化方案？ n 个结点可构造多少个不同的二叉树？ … … 更多例子可以看维基百科和这里。 而 Solutin 给出的时间复杂度，其实就是卡特兰数。 维基百科的给出的性质。

总

本以为这道题挺常规的，然后自己一直卡在解法三的理解上，查来查去，竟然查出了卡塔兰数，虽然似乎和解法三也没什么关系，但又开阔了很多思路。解法三分析出来的迭代方法，以及用映射证明卡塔兰数的求法，棒！ 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情