0022. Generate Parentheses ========================== 题目信息 -------- :题号: 0022. 括号生成 :难度: Medium :主题: 字符串、回溯、剪枝 :原题: `LeetCode 0022 `_ :重点: 在构造过程中维护合法前缀,只扩展仍可能完成为有效括号串的分支 题目重述 -------- 给定整数 ``n``,返回所有由恰好 ``n`` 对圆括号组成的有效字符串。 每个答案长度为 ``2n``,必须包含 ``n`` 个左括号和 ``n`` 个右括号。任意前缀中的右括号数量都不能超过 左括号数量,否则其中至少有一个右括号无法在左侧找到配对。``n`` 位于 ``[1, 8]``,答案顺序不限。 自建示例 -------- * 一对括号:``n = 1``,返回 ``["()"]``; * 两对括号:``n = 2``,返回 ``["(())", "()()"]``; * 三对括号:``n = 3``,共有 ``5`` 个答案:``((()))``、``(()())``、``(())()``、``()(())``、 ``()()()``; * 前缀 ``")"`` 非法,因为第一个右括号没有左侧配对; * 前缀 ``"(()"`` 合法且仍可完成,例如补成 ``"(())"``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool isValid(const std::string& text) { int balance = 0; for (char current : text) { balance += current == '(' ? 1 : -1; if (balance < 0) { return false; } } return balance == 0; } void enumerateAll( int position, std::string& path, std::vector& result ) { if (position == static_cast(path.size())) { if (isValid(path)) { result.push_back(path); } return; } path[position] = '('; enumerateAll(position + 1, path, result); path[position] = ')'; enumerateAll(position + 1, path, result); } std::vector bruteForce(int n) { std::vector result; std::string path(2 * n, '('); enumerateAll(0, path, result); return result; } void backtrack( int openRemaining, int closeRemaining, std::string& path, std::vector& result ) { if (openRemaining == 0 && closeRemaining == 0) { result.push_back(path); return; } if (openRemaining > 0) { path.push_back('('); backtrack(openRemaining - 1, closeRemaining, path, result); path.pop_back(); } if (closeRemaining > openRemaining) { path.push_back(')'); backtrack(openRemaining, closeRemaining - 1, path, result); path.pop_back(); } } std::vector prunedSearch(int n) { std::vector result; std::string path; path.reserve(2 * n); backtrack(n, n, path, result); return result; } public: std::vector generateParenthesis(int n) { return prunedSearch(n); } }; 题解 ---- 全量枚举的浪费 ~~~~~~~~~~~~~~ 长度 ``2n`` 的每个位置都可以填 ``(`` 或 ``)``,所以 ``bruteForce`` 会生成 ``2^(2n) = 4^n`` 个字符串, 再逐个检查括号数量和前缀是否合法。 问题在于,许多分支很早就已经不可能成为答案。例如前缀 ``")("`` 在第一个字符处已经出现未配对右括号, 后续追加任何字符都无法在它左侧补入左括号。继续枚举这棵子树没有意义。 合法前缀状态 ~~~~~~~~~~~~ 设当前还剩 ``openRemaining`` 个左括号和 ``closeRemaining`` 个右括号。已经使用的数量分别为 ``n - openRemaining`` 和 ``n - closeRemaining``。 合法前缀要求已使用右括号数不超过已使用左括号数,等价于: .. math:: openRemaining \le closeRemaining 初始状态为 ``(n, n)``。追加左括号会减少 ``openRemaining``,只会增加未闭合左括号数量;追加右括号会减少 ``closeRemaining``,必须确认当前确实存在尚未闭合的左括号。 受约束的分支扩展 ~~~~~~~~~~~~~~~~ 回溯只保留两种仍可能完成的选择: * ``openRemaining > 0`` 时,可以追加左括号; * ``closeRemaining > openRemaining`` 时,可以追加右括号。 第二个条件表示当前前缀中已经使用的左括号多于右括号,因此至少有一个尚未闭合的左括号可供当前右括号匹配。 若两种剩余数量相等,继续添加右括号会立即令前缀非法,只能先添加左括号。 当 ``openRemaining == 0`` 时,剩余字符只能全部为右括号;此时 ``closeRemaining > openRemaining`` 持续成立,算法会依次闭合全部左括号。当两种剩余数量都为零时,路径长度 恰为 ``2n``,可以直接记录答案,无需再次调用完整验证函数。 搜索覆盖与去重 ~~~~~~~~~~~~~~ 任意有效括号串的每个前缀都满足右括号数不超过左括号数。沿着该字符串逐字符构造时,左括号选择不会受到错误 限制;每个右括号出现前也必然存在尚未闭合的左括号,所以对应路径不会被剪掉。 回溯保留下来的每个前缀都合法,叶节点又恰好用完 ``n`` 个左括号和 ``n`` 个右括号,因此记录的字符串一定有效。 不同有效字符串至少在一个位置使用不同字符,会在该位置进入不同分支,所以每个答案只生成一次。 剪枝删除的仅是已经违反前缀条件的子树。这类前缀中的未配对右括号不可能由未来字符修复,因此被删除的分支中不存在 合法答案。 路径复用 ~~~~~~~~ ``path`` 保存当前前缀。进入子分支前追加一个字符,递归返回后删除末尾字符,路径便恢复为父状态。所有递归层 共用同一个字符串缓冲区;只有到达完整答案时才复制到 ``result``,不会让不同分支互相污染。 两个分支都从相同父路径出发。左括号分支撤销后,右括号分支看到的仍是进入本层时的原始前缀,这正是回溯中 “选择、递归、撤销”的状态边界。 复杂度分析 ~~~~~~~~~~ 有效答案数量为第 ``n`` 个 Catalan 数 ``C_n``。每个答案长度为 ``2n``,复制答案需要 ``O(n)`` 时间,因此 ``prunedSearch`` 的时间复杂度为 ``O(C_n n)``,返回结果占 ``O(C_n n)`` 空间。不计输出,递归栈和工作路径 均为 ``O(n)``。 ``bruteForce`` 生成 ``4^n`` 个候选,并对每个长度 ``2n`` 的字符串做验证,时间复杂度为 ``O(4^n n)``。