⭐ 题目日期：

小米 - 2024/10/10

🌳 题目描述：

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

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐

📝思路分析：

为了生成所有有效的括号组合，我们需要确保在生成过程中，括号的使用符合以下规则：

1. 左括号数量始终大于等于右括号数量。
2. 左括号数量和右括号数量都不能超过 n。

我们可以使用 回溯算法（Backtracking） 来解决这个问题。回溯算法是一种试探性的方法，它尝试所有可能的路径，并在发现不符合条件的情况下回退。

🌟 具体步骤

1. 定义递归函数：

   参数：

   • current: 当前生成的括号字符串。
   • left: 当前剩余的左括号数量。
   • right: 当前剩余的右括号数量。
   • result: 存储所有合法括号组合的列表。

2. 递归终止条件：

   当 left == 0 && right == 0（即括号用完时），将 current 添加到 result 列表中。

3. 递归过程：

   添加左括号：

   • 如果 left > 0，可以添加左括号，递归调用函数，left - 1。

   添加右括号：

   • 如果 right > 0，可以添加右括号，递归调用函数，right - 1。

4. 回溯：

   在递归调用返回后，撤销之前的操作，需要删除最后一个字符。

💻代码：

Java

 public List<String> generateParenthesis(int n) {
     List<String> result = new ArrayList<>();
     generateCombinations(result, new StringBuilder(), n, n);
     return result;
 }

 private void generateCombinations(List<String> result, StringBuilder current, int left, int right) {
     if (left == 0 && right == 0) {
         result.add(current.toString());
         return;
     }

     // 剪枝：如果左括号剩余数量大于右括号，无法构成合法组合
     if (left > right) {
         return;
     }

     // 尝试添加左括号
     if (left > 0) {
         current.append("(");
         generateCombinations(result, current, left - 1, right);
         current.deleteCharAt(current.length() - 1);
     }

     // 尝试添加右括号
     if (right > 0) {
         current.append(")");
         generateCombinations(result, current, left, right - 1);
         current.deleteCharAt(current.length() - 1);
     }
 }

🚵🏻复杂度分析：

时间复杂度：

空间复杂度

• 递归深度为 2n，每次递归调用需要保存状态，空间复杂度为 O(n)。
• 存储结果列表的空间复杂度取决于生成的组合数量。