题目描述
这是 LeetCode 上的22. 括号生成，难度为 Medium。
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] 复制代码
示例 2：
输入：n = 1 输出：["()"] 复制代码
提示：
- 1⩽n⩽81 \leqslant n \leqslant 81⩽n⩽8
DFS 解法
既然题目是求所有的方案，那只能爆搜了，爆搜可以使用 DFS 来做。
从数据范围 1⩽n⩽81 \leqslant n \leqslant 81⩽n⩽8 来说，DFS 应该是稳稳的 AC。
这题的关键是我们要从题目中发掘一些性质：
- 括号数为 nnn，那么一个合法的括号组合，应该包含 nnn 个左括号和 nnn 个右括号，组合总长度为 2n2n2n
- 一对合法的括号，应该是先出现左括号，再出现右括号。那么意味着任意一个右括号的左边，至少有一个左括号
其中性质 2 是比较难想到的，我们可以用反证法来证明性质 2 总是成立：
假设某个右括号不满足「其左边至少有一个左括号」，即其左边没有左括号，那么这个右括号就找不到一个与之对应的左括号进行匹配。
这样的组合必然不是有效的括号组合。
使用我们 20. 有效的括号 的思路（栈）去验证的话，必然验证不通过。
掌握了这两个性质之后，我们可以设定一个初始值为 0 的得分值，令往组合添加一个 ( 得分值 + 1，往组合添加一个 ) 得分值 -1。
这样就有：
- 一个合法的括号组合，最终得分必然为 0 （左括号和右括号的数量相等，对应了性质 1）
- 整个
DFS过程中，得分值范围在[0, n]（得分不可能超过n意味着不可能添加数量超过n的左括号，对应了性质 1；得分不可能为负数，意味着每一个右括号必然有一个左括号进行匹配，对应性质 2）
代码：
class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<>(); dfs(0, n * 2, 0, n, "", ans); return ans; } /** * i: 当前遍历到位置 * n: 字符总长度 * score: 当前得分，令 '(' 为 1， ')' 为 -1 * max: 最大得分值 * path: 当前的拼接结果 * ans: 最终结果集 */ void dfs(int i, int n, int score, int max, String path, List<String> ans) { if (i == n) { if (score == 0) ans.add(path); } else { // 如果添加左括号后不超过 max（有效值），则可以添加 if (score + 1 <= max) { dfs(i + 1, n, score + 1, max, path + "(", ans); } // 如果添加右括号后不少于 0（有效值），则可以添加 if (score - 1 >= 0) { dfs(i + 1, n, score - 1, max, path + ")", ans); } } } } 复制代码
- 时间复杂度：放置的左括号数量为
n，右括号的个数总是小于等于左括号的个数，典型的卡特兰数问题。复杂度为 O(C2nn)O(C_{2n}^n)O(C2nn) - 空间复杂度：O(1)O(1)O(1)
总结
将「有效括号问题」转化为「分值有效性」的数学判定，算是三叶比较习惯的一种做法。
事实上，不仅仅是括号问题。此类「成对匹配」相关的题型都能转化为此类模型进行求解。
这两天会找一些类似的题目来加强大家对这种技巧的掌握 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.22 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
