393，括号生成
Nothing that has meaning is easy. Easy doesn’t enter into grown-up life.
凡是有意义的事都不会容易，成年人的生活里没有容易二字。
问题描述
数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
问题分析
通过观察我们可以发现，生成的任何括号组合中都有两个规律：
1，括号组合中左括号的数量等于右括号的数量
2，括号组合中任何位置左括号的数量都是大于等于右括号的数量
第一条很容易理解，我们来看第二条，比如有效括号"(())()"，在任何一个位置右括号的数量都不大于左括号的数量，所以他是有效的。如果像这样"())()"第3个位置的是右括号，那么他前面只有一个左括号，而他和他前面的右括号有2个，所以无论如何都不能组合成有效的括号。搞懂了上面的原理，我们就以n等于2为例来画个图看一下
看到上面的图我们很容易想到二叉树的前序遍历，可以看下之前写的373，数据结构-6,树，所以这里我们可以参考一下，二叉树的前序遍历代码如下
public static void preOrder(TreeNode tree) { if (tree == null) return; System.out.printf(tree.val + ""); preOrder(tree.left); preOrder(tree.right);}使用的是递归的方式，有一个终止条件，然后后面是两个递归的调用，所以这题的参考代码如下
1public List<String> generateParenthesis(int n) {
2 List<String> res = new ArrayList<>();
3 dfs(res, n, n, "");
4 return res;
5}
6
7private void dfs(List<String> res, int left, int right, String curStr) {
8 /**
9 * 这里有终止条件
10 * return
11 */
12 //选择左括号
13 dfs(res, left - 1, right, curStr + "(");
14 // 选择右括号
15 dfs(res, left, right - 1, curStr + ")");
16}
其中left是左括号剩余的数量，right是右括号剩余的数量。代码的大致轮廓已经出来了，关键是终止条件。根据上面的分析，我们知道如果左括号和右括号剩余可选数量都等于0的时候，说明找到了有效的括号组合。如果左括号剩余可选数量为0的时候，我们不能再选择左括号了，但可以选择右括号。如果左括号剩余数量大于右括号剩余数量说明之前选择的是无效的。所以终止条件就呼之欲出了，最终代码如下
1public List<String> generateParenthesis(int n) {
2 List<String> res = new ArrayList<>();
3 dfs(res, n, n, "");
4 return res;
5}
6
7private void dfs(List<String> res, int left, int right, String curStr) {
8 if (left == 0 && right == 0) { // 左右括号都不剩余了，说明找到了有效的括号
9 res.add(curStr);
10 return;
11 }
12 //左括号只有剩余的时候才可以选，如果左括号的数量已经选完了，是不能再选左括号了。
13 //如果选完了左括号我们是还可以选择右括号的。
14 if (left < 0)
15 return;
16 // 如果右括号剩余数量小于左括号剩余的数量，说明之前选择的无效
17 if (right < left)
18 return;
19 //选择左括号
20 dfs(res, left - 1, right, curStr + "(");
21 //选择右括号
22 dfs(res, left, right - 1, curStr + ")");
23}
动态规划
我们用dp[i]表示的是n等于i的时候生成的有效括号组合，那么递推公式就是
dp[i]="("+dp[m]+")"+dp[k]
其中m+k=i-1
因为他再加上我们添加的一对括号正好是i，（其中m是从0到i-1）所以这里我们需要枚举m的所有值。主要代码如下
for (int m = 0; m < i; m++) { int k = i - 1 - m; List<String> str1 = dp[m]; List<String> str2 = dp[k]; for (String s1 : str1) { for (String s2 : str2) { cur.add("(" + s1 + ")" + s2); } }}这题的边界条件是dp[0]=""，因为0的时候是没有括号的。所以完整代码如下
1public static List<String> generateParenthesis(int n) {
2 List<String>[] dp = new List[n + 1];
3 List<String> dp0 = new ArrayList<>();
4 dp0.add("");
5 dp[0] = dp0;
6 for (int i = 1; i <= n; i++) {
7 List<String> cur = new ArrayList<>();
8 for (int m = 0; m < i; m++) {
9 int k = i - 1 - m;
10 List<String> str1 = dp[m];
11 List<String> str2 = dp[k];
12 for (String s1 : str1) {
13 for (String s2 : str2) {
14 cur.add("(" + s1 + ")" + s2);
15 }
16 }
17 }
18 dp[i] = cur;
19 }
20 return dp[n];
21}
我们就用n等于3来测试一下打印的结果
public static void main(String args[]) { System.out.println(Arrays.toString(generateParenthesis(3).toArray()));}运行结果如下
[()()(), ()(()), (())(), (()()), ((()))]动态规划改递归
我们看到上面动态规划中核心代码是dp[m]和dp[k]的组合，而dp[m]和dp[k]分别表示的是n等于m和k的时候有效括号的组合，所以如果函数
List<String> generateParenthesis(int n)
表示的是n对有效括号的组合，那么
List<String> generateParenthesis(int m)
和
List<String> generateParenthesis(int k)
分别表示的是m对和k对有效括号的组合，所以上面的核心代码我们可以这样改
for (int m = 0; m < n; m++) { int k = n - m - 1; List<String> first = generateParenthesis(m); List<String> second = generateParenthesis(k); for (String left : first) { for (String right : second) { list.add("(" + left + ")" + right); } }}所以完整代码如下
1public static List<String> generateParenthesis(int n) {
2 List<String> list = new ArrayList<>();
3 if (n == 0) {//边界条件的判断
4 list.add("");
5 return list;
6 }
7 for (int m = 0; m < n; m++) {
8 int k = n - m - 1;
9 List<String> first = generateParenthesis(m);
10 List<String> second = generateParenthesis(k);
11 for (String left : first) {
12 for (String right : second) {
13 list.add("(" + left + ")" + right);
14 }
15 }
16 }
17 return list;
18}
总结
这题可能最容易想到的是暴力求解，就是生成所有的组合，然后再判断这些组合哪些是有效的，但这种效率很差，所以这里没写。上面第一种解法很好的利用了有效括号的特性，无效括号直接舍去，达到剪枝的目的。下面两种解法原理都是一样的，只不过一个使用的是动态规划，一个使用的是递归，都是根据已经生成的长度为i-1的有效括号，然后推出长度为i的有效括号。
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧