括号
难度:
标签:
题目描述
Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.
Note: The result set should not contain duplicated subsets.
For example, given n = 3, the result should be:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
代码结果
运行时间: 48 ms, 内存: 15.1 MB
/*
* 问题思路：
* 使用 Java Stream 的特性来生成所有合法的括号组合。
* 使用递归的方法生成所有可能的括号序列。
* 当字符串达到所需长度时，将其转换为流并收集到一个 List 中。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class GenerateParenthesesStream {
public List<String> generateParenthesis(int n) {
return generate("", 0, 0, n).collect(Collectors.toList());
}
private Stream<String> generate(String current, int open, int close, int max) {
// 当达到最大长度时，返回当前序列
if (current.length() == max * 2) {
return Stream.of(current);
}
Stream<String> result = Stream.empty();
// 递归生成所有可能的括号组合
if (open < max) {
result = Stream.concat(result, generate(current + "(", open + 1, close, max));
}
if (close < open) {
result = Stream.concat(result, generate(current + ")", open, close + 1, max));
}
return result;
}
}
解释
方法:
该题解使用回溯法来生成所有可能的合法括号组合。函数 `backtrack(path, stack)` 递归地构建括号串，其中 `path` 用于存储当前的括号组合，`stack` 用于模拟一个栈来确保括号的合法性（即，始终保持栈中的左括号数量不少于右括号）。递归终止条件是当 `path` 的长度达到 `2 * n` 且 `stack` 为空时，表示找到一个合法的组合。在递归过程中，基于当前 `stack` 的状态，选择添加 '(' 或 ')'。如果 `stack` 为空，只能添加 '('；如果 `stack` 的长度为 `n`（即已经添加了所有的左括号），只能添加 ')'；否则，既可以添加 '(' 也可以添加 ')'。每次添加后，递归调用 `backtrack` 继续构建路径，之后撤销该步骤（回溯），以尝试其他可能性。
时间复杂度:
O(4^n / sqrt(n))
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在回溯过程中，选择添加'('后立即在递归调用后将其从stack中移除，这种处理方式的目的是什么？
▷🦆
在实现中，如果stack的长度等于n，即已经添加了所有左括号，这里只能添加')'的逻辑是否充分考虑了所有可能的括号添加顺序？
▷🦆
代码中的递归终止条件是path长度等于2n且stack为空，但是为什么还需要检查stack是否为空？
▷🦆
递归函数backtrack中，path和stack分别代表了什么具体的逻辑角色和功能，这与传统的回溯算法框架有何异同？
▷