【力扣高频题】021.括号生成

上篇文章我们学习了判断一个字符串是否是有效的括号顺序 : 有效的括号 。今天我们继续来学习一道有关有效括号的 中等难度 题目。

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入： n = 3

输出： [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:

输入： n = 1

输出： [“()”]

• 提示：
• 1 <= n <= 8

思路分析

对于 n n n 对括号，需要 2 n 2n 2n 个位置来存放。

本题我们采用 从左到右 的递归来思考。考虑每个位置上能够存放什么类型的括号。

当然，最简单的思路就是枚举所有可能的情况。由于我们已经定好了总的括号数量为 2 n 2n 2n，因此只要在枚举完后检查每种枚举结果是否是有效的括号组合即可。（只要合法，数量一定是 n n n 对）

合法性检查：

1. 维护计数变量count = 0，遍历序列，遇到左括号加一，遇到右括号减一。
2. 若中途出现count < 0的情况，说明此时序列中，右括号多于左括号，不合法。
3. 若遍历结束，count == 0，说明左右括号数量相等且合法，否则说明左括号多于右括号，不合法。

暴力递归

// 不剪枝
public static List<String> generateParenthesis(int n) {
   char[] path = new char[n << 1];
   List<String> ans = new ArrayList<>();
   process(path, 0, ans);
   return ans;
}

public static void process(char[] path, int index, List<String> ans) {
   if (index == path.length) {
       if (isValid(path)) {
           ans.add(String.valueOf(path));
       }
   } else {
       path[index] = '(';
       process(path, index + 1, ans);
       path[index] = ')';
       process(path, index + 1, ans);
   }
}

public static boolean isValid(char[] path) {
   int count = 0;
   for (char cha : path) {
       count = (cha == '(') ? count+1 : count-1;
       if (count < 0) {
           return false;
       }
   }
   return count == 0;
}

思路优化

对于上面的暴力递归来说，生成了许多无效的解，没有做到合理的剪枝。其原因在于，生成解的 过程中 并没有做有效性检查（把检查放在了最后）。

因此，我们考虑增加一些变量的限制，使其仅生成有效解，大大减少运算量。

在递归中增加两个参数，lMinusR和leftRest：

• lMinusR表示在path[0 ... index-1]已经做过的决策中左括号-右括号的数量。
• leftRest表示还有多少左括号可以使用，即总数 n - 已经使用过的。

剪枝代码

public static List<String> generateParenthesis(int n) {
   char[] path = new char[n << 1];
   List<String> ans = new ArrayList<>();
   process(path, 0, 0, n, ans);
   return ans;
}

public static void process(char[] path, int index, int lMinusR, int leftRest, List<String> ans) {
   if (index == path.length) {
       ans.add(String.valueOf(path));
   } else {
       if (leftRest > 0) {
           path[index] = '(';
           process(path, index + 1, lMinusR + 1, leftRest - 1, ans);
       }
       if (lMinusR > 0) {
           path[index] = ')';
           process(path, index + 1, lMinusR - 1, leftRest, ans);
       }
   }
}

代码分析

1. 当下标来到最后时，生成结束，加入到答案集合中。
2. 如果左括号还有剩余，说明此时还可以放入左括号。继续后移，此时lMinusR + 1，能够使用的左括号减少一个。
3. 如果lMinusR > 0，说明此时可以放入右括号。继续后移，此时lMinusR - 1，能够使用的左括号不变。

小伙伴们可以再认真思考下该代码哦~~~

最后

上次给大家介绍的 面试八股文小程序 评价 杠杠滴~~

最近又和朋友一起合作开发了算法全套刷题 ，专门针对于 解决面试中算法问题 学习的课程，有需要的小伙伴可以去看看，保证你在面试中如鱼得水。

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！
回复「1024」获取 Java 面试资源 ~
回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

在看 + 转发

让你的小伙伴们一起来学算法吧！！