题目要求：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
生成有效括号组合
这道题是经典的回溯算法题目，核心思路是：通过递归尝试添加/右括号，始终保证在左括号数量>=右括号数量，最终生成所有合法组合。
核心逻辑讲解
- 回溯算法：递归尝试所有可能的括号组合，遇到无效组合直接回溯（不继续递归）。
- 两个关键规则（保证括号有效）：
左括号数量不能超过n（最多只能用n个左括号）；
右括号数量必须小于左括号数量（避免出现())这种无效组合）。 - 终止条件：当字符串长度等于2*n时，说明左右括号都用完了，直接加入结果集。
执行流程（以n=2为例）
- 初始：current = "",open = 0,close = 0
- 加左括号 -> "(",1,0
- 再加左括号 -> "((",2,0
- 只能加右括号->"(()",2,1
- 再加右括号->"(())",2,2(长度 = 4，加入结果)
- 回溯，尝试另一条路径->"()",1,1
- 加左括号->"()(",2,1
- 加右括号->"()()",2,2(加入结果)
最终得到["(())","()()"]。
总结
- 用回溯算法递归生成所有组合，通过两个规则过滤无效括号；
- 时间复杂度：O(n+11C2nn)（卡特兰数，有效组合的总数）
- 空间复杂度：O(n)（递归栈深度，最多递归 2n 层）
条件 1：open < n
保证左括号不超过 n 个。
条件 2：close < open
保证右括号永远不会比左括号多，避免出现 ()) 这种无效情况。
绝对不能用close < n 代替 close < open！
必须时刻保证左括号数量大于等于右括号数量，如果条件替换成close<n，会出现以下情况：
假设n = 2
()，此时open = 1,close = 1
- 前面已经处理了"()()"和"(())"两种情况,先"(())",后"()()"
- 回溯退回到()(这一层，由于这一层的两个if都执行完了->也return
- 回溯到()这一层，由这一层上一次递归的场景是()( 可知执行的是添加左括号的递归，因此接下来执行的是4. 右括号的递归,此时close<n,执行右括号的递归，())
- 再进入())这一层的递归，由于open<n执行左括号的递归，最终result结果为"())("，出现了括号匹配错误的情况。
综上可知，为了避免出现这种括号错误匹配的问题，我们需要时刻保持左括号的数量大于等于右括号的数量，即close<open,这样当递归回溯到()时，由于close并不小于open的数量，因此不会进入执行())的递归
完整Java代码实现如下：
import java.util.ArrayList;
import java.util.List;
public class GenerateParentheses {
public List<String> generateParenthesis(int n) {// 存储最终结果List<String> result = new ArrayList<>();// 回溯递归：当前字符串、左括号数、右括号数、目标对数、结果集backtrack("", 0, 0, n, result);return result;
}/*** 回溯核心方法* @param current 当前拼接的括号字符串* @param open 已使用的左括号数量* @param close 已使用的右括号数量* @param n 目标括号对数* @param result 结果集合*/
private void backtrack(String current, int open, int close, int n, List<String> result) {// 递归终止条件：字符串长度 = 2*n（左右括号都用完了）if (current.length() == 2 * n) {result.add(current);return;}// 1. 可以添加左括号：左括号数量 < nif (open < n) {backtrack(current + "(", open + 1, close, n, result);}// 2. 可以添加右括号：右括号数量 < 左括号数量（保证有效）if (close < open) {backtrack(current + ")", open, close + 1, n, result);}
}// 测试示例
public static void main(String[] args) {GenerateParentheses solution = new GenerateParentheses();// 测试 n=3System.out.println(solution.generateParenthesis(3));// 输出：["((()))","(()())","(())()","()(())","()()()"]
}
}