原题地址:. - 力扣（LeetCode）
题目描述
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]提示：
1 <= n <= 8
实现思路
题目要求生成所有有效的括号组合。有效的括号组合是指每个左括号
(都有对应的右括号)，且在任意前缀中左括号的数量不少于右括号的数量。思路：
- 回溯法：使用回溯法生成所有可能的括号组合。可以用一个字符数组
current来存储当前的组合。- 递归生成：在每个位置上可以选择放入左括号或右括号。
- 验证有效性：在生成完整的组合后，通过一个辅助函数检查该组合是否有效。
- 结束条件：当字符数组填满时，检查组合的有效性，并将有效的组合添加到结果列表中。
源码实现
class Solution {
public List<String> generateParenthesis(int n) {
// 创建一个列表来存储所有有效的括号组合
List<String> combinations = new ArrayList<String>();
// 调用递归函数生成所有可能的组合
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
// 如果当前位置到达数组末尾
if (pos == current.length) {
// 检查当前组合是否有效
if (valid(current)) {
// 如果有效，添加到结果列表
result.add(new String(current));
}
} else {
// 在当前位置放入左括号
current[pos] = '(';
generateAll(current, pos + 1, result); // 递归生成下一位置的组合
// 在当前位置放入右括号
current[pos] = ')';
generateAll(current, pos + 1, result); // 递归生成下一位置的组合
}
}
public boolean valid(char[] current) {
int balance = 0; // 用于跟踪括号的平衡情况
for (char c : current) {
if (c == '(') {
++balance; // 左括号增加平衡
} else {
--balance; // 右括号减少平衡
}
// 如果平衡小于零，说明右括号多于左括号，组合无效
if (balance < 0) {
return false;
}
}
// 只有当平衡为零时，才说明所有括号有效
return balance == 0;
}
}
复杂度评估
时间复杂度：
- 最坏情况下，算法会生成
O(2^(2n))种组合，这是由于每个位置都有两种选择（(或)），且组合的长度为2n。- 然而，实际上有效的组合数量是 Catalan 数
C(n) = (2n)! / ((n+1)! * n!)，因此实际生成的组合数会远少于O(2^(2n))。空间复杂度：
- 使用的空间主要是
result列表和current数组。current数组的长度为2n，而result列表存储所有有效组合，最多为O(C(n))。- 总体空间复杂度为
O(n)（用于存储current数组）加上O(C(n))（存储有效组合），所以可以认为是O(C(n))
