[Java·算法·中等]LeetCode22. 括号生成

👉️ 力扣原文

题目

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

示例

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

分析思路1

递归和回溯的方法：

1. 定义一个函数来生成括号，该函数需要接收三个参数：剩余左括号数量、剩余右括号数量、当前生成的括号字符串。
2. 如果剩余左括号数量和剩余右括号数量都为0，则说明已经生成了一个完整的括号字符串，将其加入结果集。
3. 如果剩余左括号数量大于0，则可以在当前括号字符串后面添加一个左括号，并递归调用函数。
4. 如果剩余右括号数量大于剩余左括号数量，则可以在当前括号字符串后面添加一个右括号，并递归调用函数。

题解1

class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();gen(n , n , "", res);return res;}private void gen(int left, int right, String str, List<String> res){if(left == 0 && right == 0){res.add(str);return;}if(left > 0){gen(left - 1,right, str+"(", res );}if(right > left){gen(left, right - 1, str+")", res);}}}

执行结果

分析思路2

另一种递归的思路，效率不是很高。

1. 当n=1时，只有一种合法的括号组合"()"。
2. 当n>1时，可以在n-1对括号的基础上，将"()"插入到每一对括号中间，得到n对括号的所有合法组合。
3. 为了避免重复，使用HashSet来存储所有的括号组合。
4. 最后将HashSet转换成ArrayList并返回即可。

题解2

class Solution {public static List<String> generateParenthesis(int n){if (n == 1){return Arrays.asList("()");}HashSet<String> set = new HashSet<>();for (String str : generateParenthesis(n - 1)){for (int i = 0; i <= str.length()/2; i++) {set.add(str.substring(0,i) + "()" + str.substring(i,str.length()));}}return new ArrayList<>(set);}}

执行结果

分析思路3

动态规划

1. 定义一个dp数组，其中dp[i]表示i对括号的所有合法组合。
2. 初始化dp[0]为""，表示0对括号时只有一种合法组合。
3. 对于每个i，遍历j从0到i-1，将dp[j]和dp[i-j-1]拼接在一起，组成新的括号组合。
4. 在拼接时，需要保证左括号数量等于右括号数量，否则组合是不合法的。
5. 最后返回dp[n]即可。

题解3

class Solution {public static List<String> generateParenthesis(int n) {List<String>[] dp = new List[n + 1];dp[0] = Arrays.asList("");for (int i = 1; i <= n; i++) {dp[i] = new ArrayList<>();for (int j = 0; j < i; j++) {for (String left : dp[j]) {for (String right : dp[i - j - 1]) {dp[i].add("(" + left + ")" + right);}}}}return dp[n];}}

执行结果