括号生成
难度:
标签:
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
代码结果
运行时间: 52 ms, 内存: 15.1 MB
/*
* This solution utilizes a stream-based approach to generate valid parentheses.
* We still use backtracking internally but convert the list to a stream at the end.
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
public class GenerateParenthesesStream {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result.stream().collect(Collectors.toList());
}
private void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) {
result.add(current);
return;
}
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}
}
解释
方法:
该题解使用回溯法生成有效的括号组合。通过递归的方式，不断地尝试添加左括号和右括号，同时使用一个栈来记录当前未匹配的左括号数量。在递归过程中，根据栈的大小和已生成的括号数量，选择添加左括号或右括号。当生成的括号数量达到 2*n，且栈为空时，说明生成了一个有效的括号组合，将其加入结果列表中。
时间复杂度:
O((4^n) / (n^(1/2)))
空间复杂度:
O((4^n) / (n^(1/2)))
代码细节讲解
🦆
为什么在选择括号类型时，栈的大小会直接决定可以添加的括号类型？
▷🦆
题解中提到的`卡特兰数公式`如何应用于有效括号的数量计算？能否解释其数学依据？
▷🦆
递归函数`backtrack`在进行回溯时，为何需要对括号添加和移除操作同时进行栈的出栈和入栈操作？
▷🦆
在递归生成括号的过程中，`if len(path) >= 2 * n`的检查是为了什么？是否和括号生成完成有关？
▷🦆
题解中提到的时间复杂度和空间复杂度计算，是否可以通过具体的例子详细说明其如何被计算？
▷🦆
在处理递归的过程中，为什么要单独处理栈大小为0或超过n的情况，这与有效括号生成的逻辑有何关系？
▷