【中等】题解力扣22：括号生成
题目详情
数字 n 代表生成括号的对数，设计一个函数生成所有可能的并且有效的括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
解题思路
使用回溯法（深度优先搜索） 生成所有有效括号组合，核心思路如下：
- 有效括号条件：
- 左括号数量不能超过
n。 - 右括号数量不能超过左括号（确保有效性）。
- 递归终止条件：当前字符串长度达到
2n时，将结果加入列表。 - 递归过程：
- 若左括号数量
< n，添加左括号并递归。 - 若右括号数量
< 左括号数量，添加右括号并递归。
- 回溯：每次递归后删除最后一个字符，尝试其他组合。
- 优化：使用
StringBuilder避免字符串拼接开销，减少内存消耗。
代码实现（Java版）
import java.util.ArrayList;
import java.util.List;class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(result, new StringBuilder(), 0, 0, n);return result;}private void backtrack(List<String> result, StringBuilder current, int left, int right, int n) {if (current.length() == 2 * n) {result.add(current.toString());return;}if (left < n) {current.append('(');backtrack(result, current, left + 1, right, n);current.deleteCharAt(current.length() - 1); // 回溯}if (right < left) {current.append(')');backtrack(result, current, left, right + 1, n);current.deleteCharAt(current.length() - 1); // 回溯}}
}
代码说明
- 初始化：
result存储最终结果，StringBuilder current动态构建当前组合。
- 回溯函数：
- 参数：
left（已用左括号数）、right（已用右括号数）、n（总对数）。 - 终止条件：
current.length() == 2 * n时保存有效组合。 - 左括号分支：当
left < n时，添加(并递归。 - 右括号分支：当
right < left时，添加)并递归。 - 回溯操作：递归返回后删除末尾字符，恢复状态尝试其他分支。
- 效率关键：
- 通过条件剪枝避免无效组合。
StringBuilder减少字符串操作开销。
提交详情（执行用时、内存消耗）
