LeetCode题练习与总结：括号生成

一、题目

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

二、解题思路

1. 问题定义：这是一个经典的回溯问题。我们需要生成所有可能的括号组合，这些组合必须满足括号正确匹配的条件。
2. 递归思路：我们可以定义一个递归函数，该函数在每一步决定是添加一个左括号、右括号还是停止添加。在每一步，我们需要检查当前的括号组合是否有效，即左括号的数量是否大于右括号的数量。
3. 回溯：如果当前组合无效（例如，添加了一个右括号但左括号数量不足），我们需要撤销这个步骤（回溯），然后尝试其他可能的选项。
4. 结果收集：我们需要一个列表来收集所有有效的括号组合。每当我们完成一个有效的组合时，就将其添加到结果列表中。

三、具体代码

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List generateParenthesis(int n) {
        List result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }
 
    private void backtrack(List result, StringBuilder current, int open, int close, int max) {
        // 如果当前字符串的长度等于2 * n，说明已经生成了一个有效的组合
        if (current.length() == 2 * max) {
            result.add(current.toString());
            return;
        }
 
        // 添加一个左括号
        if (open < max) {
            current.append('(');
            backtrack(result, current, open + 1, close, max);
            current.deleteCharAt(current.length() - 1); // 回溯，移除最后一个字符
        }
 
        // 添加一个右括号
        if (close < open) {
            current.append(')');
            backtrack(result, current, open, close + 1, max);
            current.deleteCharAt(current.length() - 1); // 回溯，移除最后一个字符
        }
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 递归函数 backtrack 会为每一对括号进行两次递归调用：一次是添加左括号，一次是添加右括号。
• 对于每一对括号，我们有三种选择：添加左括号、添加右括号、不添加（回溯）。
• 因此，对于 n 对括号，我们有 3^n 种不同的组合方式。
• 但是，由于括号必须成对出现，所以实际上我们只需要考虑所有可能的配对方式，即 C(2n, n) / 2，这大约是 4^n / 2。
• 每次递归调用都需要一定的空间来存储当前的字符串和递归状态。
• 因此，最坏情况下的时间复杂度是 O(4^n / 2)，但由于回溯的存在，实际执行的递归调用次数会少于这个数量。

2. 空间复杂度

• 递归调用栈的深度最多为 n，因为我们需要 n 对括号来形成一个有效的组合。
• 结果列表 result 存储所有有效的括号组合，其数量最多为 C(2n, n) / 2，这大约是 4^n / 2。
• 递归调用栈的空间加上结果列表的空间构成了总的空间复杂度。
• 因此，总的空间复杂度是 O(n + 4^n / 2)。在实际应用中，由于我们不会探索所有可能性，结果列表的大小通常远小于 4^n / 2，所以实际的空间复杂度主要取决于结果列表的大小。

五、总结知识点

1. 递归（Recursion）：

• 递归是一种通过函数自己调用自己来重复执行代码的方法。
• 在这个问题中，backtrack 方法递归地构建所有可能的括号组合。

2. 回溯（Backtracking）：

• 回溯是一种通过在递归过程中撤销之前步骤来避免错误解决方案的算法策略。
• 当添加的括号不满足有效组合的条件时（例如，添加了多余的右括号），代码通过删除最后一个字符来回溯。

3. 字符串构建（String Building）：

• 使用 StringBuilder 类来构建和修改字符串。
• StringBuilder 是一个可变的字符串序列，它比 String 类型更高效，尤其是在需要多次修改字符串时。

4. 条件语句（Conditional Statements）：

• 使用 if 语句来控制逻辑流程，决定何时添加左括号或右括号。

5. 列表操作（List Operations）：

• 使用 ArrayList 来存储和返回结果。
• ArrayList 是一个动态数组，可以方便地添加、删除和访问元素。

6. 字符串操作（String Operations）：

• 使用 toString() 方法将 StringBuilder 对象转换为字符串。
• 使用 deleteCharAt(int index) 方法从 StringBuilder 中删除指定位置的字符。

7. 算法逻辑（Algorithm Logic）：

• 理解并实现生成所有有效括号组合的逻辑。
• 确保左括号的数量始终小于或等于右括号的数量，以避免无效的组合。

8. 边界条件处理（Boundary Conditions）：

• 当 current 的长度达到 2 * max 时，表示已经生成了一个有效的括号组合，这时将当前字符串添加到结果列表中。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。