22. 括号生成

---

题目

描述： 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例： 示例 1:

输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入: n = 1
输出: ["()"]

---

解题思路

核心方法

回溯法：

1. 有效括号的条件：

• 左括号的数量不超过 n。
• 右括号的数量不超过左括号的数量。

2. 路径选择：维护一个字符串 temp，存储当前已生成的括号组合。
3. 递归终止条件：当左括号和右括号的数量均等于 n 时，将当前字符串加入结果列表。
4. 回溯过程：

• 若左括号数量小于 n，可以添加左括号，递归进入下一层（左括号数量+1）。
• 若右括号数量小于左括号数量，可以添加右括号，递归进入下一层（右括号数量+1）。
• 递归返回后，自动回溯到上一层，尝试其他选择。

---

代码实现

回溯法（Java）

import java.util.*;

class Solution {
    List<String> ans = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        dfs(n, "", 0, 0);
        return ans;
    }
    
    public void dfs(int n, String temp, int left, int right) {
        // 剪枝：无效括号直接返回
        if (left > n || right > left) return;
        // 终止条件：生成了 n 对有效括号
        if (left == n && right == n) {
            ans.add(temp);
            return;
        }
        // 尝试添加左括号
        dfs(n, temp + "(", left + 1, right);
        // 尝试添加右括号
        dfs(n, temp + ")", left, right + 1);
    }
}

---

复杂度分析

• 时间复杂度：O(4^n / √n)，这是第 n 个卡特兰数的渐近复杂度，对应有效括号组合的数量。
• 空间复杂度：O(n)，递归栈的深度为 2n（生成的字符串长度），临时字符串的空间也为 2n。

---

总结

1. 回溯法通过剪枝策略（避免生成无效括号），能够高效生成所有有效的括号组合。
2. 核心逻辑是控制左括号和右括号的数量，确保右括号的数量始终不超过左括号的数量。
3. 该方法的时间复杂度由卡特兰数决定，适用于 n 较小的场景（题目限制 1 <= n <= 8）。

---