leetcode22:括号问题

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

问题分析

题目性质

该问题属于组合生成问题，输入是一个数字 nn，代表括号对数，输出是一个包含所有可能且有效的括号组合的列表。有效的括号组合要求：

1. 每个组合中左括号和右括号数量相等。
2. 任意前缀的右括号数量不能超过左括号数量。

输入条件

• nn：整数，表示括号对数。
• 1≤n≤81 \leq n \leq 8

输出条件

• 一个字符串列表，包含所有有效的括号组合。

边界条件

• n=1n = 1：只有一个组合 ["()"]。
• nn 较大时，输出的组合数量呈指数级增长。

解题步骤

步骤1：算法设计

此问题可以用回溯法解决。通过递归地尝试添加左括号和右括号，同时确保每一步生成的部分字符串都满足有效性条件。

回溯法逻辑：

1. 使用两个计数器：left 表示已使用的左括号数量，right 表示已使用的右括号数量。
2. 初始条件：left = 0, right = 0, 初始字符串为空。
3. 在每一步递归中：
   • 如果 left < n，可以添加左括号。
   • 如果 right < left，可以添加右括号。
   • 当 left == n 且 right == n 时，生成一个完整的有效括号组合。
4. 递归终止条件：left 和 right 都达到 nn。

步骤2：时间和空间复杂度

• 时间复杂度：生成 C2nn/(n+1)C_{2n}^n / (n+1) 个有效组合，递归深度为 2n2n，时间复杂度为 O(4n/n)O(4^n / \sqrt{n})。
• 空间复杂度：递归栈的深度为 2n2n，每次递归会保存部分路径，空间复杂度为 O(n)O(n)。

步骤3：代码实现

以下是实现代码，使用 C++ 并附带详细中文注释。

// 回溯函数
void backtrack(vector<string>& result, string current, int left, int right, int n) {
    // 如果当前组合已经完成
    if (left == n && right == n) {
        result.push_back(current);
        return;
    }
    // 如果可以添加左括号，尝试添加
    if (left < n) {
        backtrack(result, current + "(", left + 1, right, n);
    }
    // 如果可以添加右括号，尝试添加
    if (right < left) {
        backtrack(result, current + ")", left, right + 1, n);
    }
}

// 主函数
vector<string> generateParenthesis(int n) {
    vector<string> result;
    backtrack(result, "", 0, 0, n);
    return result;
}

解决问题的启发

1. 递归+回溯是解决生成类问题的经典方法：
   • 回溯法在生成所有可能性时，动态裁剪不满足条件的分支，提升了效率。
2. 问题建模的重要性：括号组合可以抽象为“左右平衡”的动态构造问题，利用递归函数中的参数控制状态。

实际生活中的应用

场景：任务调度

在任务调度场景中，括号生成问题可以用于解决任务依赖问题。例如：

• (( 对应“开始任务”和“完成任务”。
• 合法的括号组合对应有效的任务执行顺序。

具体示例：

假设有 n=3个任务，每个任务需要“启动”和“结束”，且不能在启动前结束任务。通过上述算法，可以生成所有合法的任务执行顺序。

实现方法：

1. 使用括号生成算法生成所有合法任务序列。
2. 将任务映射到括号组合中：
   • ( 映射为“启动任务”。
   • ) 映射为“结束任务”。
3. 在任务依赖场景下验证这些序列。

通过这样的模型化方法，可以在分布式系统、自动化任务执行中应用。