题目描述给你一个由若干括号和字母组成的字符串s删除最小数量的无效括号使得输入的字符串有效。返回所有可能的结果。答案可以按任意顺序返回。示例 1输入s ()())()输出[(())(),()()()]示例 2输入s (a)())()输出[(a())(),(a)()()]示例 3输入s )(输出[]解题思路方法一DFS 剪枝最优推荐思路第一步统计需要删除的左右括号数量用一次遍历模拟括号匹配遇到(时leftToRemove遇到)时如果leftToRemove 0则配对成功leftToRemove--否则这个)多余rightToRemove第二步DFS 尝试删除对每个括号字符有两种选择保留加入当前路径删除如果还有删除配额leftToRemove 0或rightToRemove 0则跳过关键剪枝当前路径中右括号数量不能超过左括号rightCount leftCount时剪枝剩余字符数不足以完成所需删除时剪枝相邻相同括号只删第一个避免重复解去重用HashSet存储结果代码实现class Solution { unordered_setstring result; int leftToRemove, rightToRemove; string s; public: vectorstring removeInvalidParentheses(string _s) { s _s; leftToRemove rightToRemove 0; // 第一步统计多余的左右括号数量 for (char c : s) { if (c () { leftToRemove; } else if (c )) { if (leftToRemove 0) { leftToRemove--; } else { rightToRemove; } } } dfs(0, , 0, 0); return vectorstring(result.begin(), result.end()); } void dfs(int index, string current, int leftCount, int rightCount) { // 剪枝右括号多于左括号无效 if (rightCount leftCount) return; if (index s.size()) { if (leftToRemove 0 rightToRemove 0) { result.insert(current); } return; } char c s[index]; if (c () { // 选择1保留 dfs(index 1, current c, leftCount 1, rightCount); // 选择2删除如果有配额 if (leftToRemove 0) { leftToRemove--; dfs(index 1, current, leftCount, rightCount); leftToRemove; } } else if (c )) { // 选择1保留 dfs(index 1, current c, leftCount, rightCount 1); // 选择2删除如果有配额 if (rightToRemove 0) { rightToRemove--; dfs(index 1, current, leftCount, rightCount); rightToRemove; } } else { // 字母直接保留 dfs(index 1, current c, leftCount, rightCount); } } };复杂度分析时间复杂度O(2^P × n)P 是括号总数≤20最坏情况遍历所有子集空间复杂度O(n)递归栈深度方法二BFS 逐层删除思路BFS 逐层删除一个括号直到找到有效的字符串。因为 BFS 按层遍历第一次找到的有效字符串就是删除数量最少的 。用queue存储当前层的所有字符串用visited集合去重处理完一层后如果找到了有效字符串只收集这一层的所有结果不再继续下一层代码实现class Solution { public: vectorstring removeInvalidParentheses(string s) { vectorstring result; unordered_setstring visited{s}; queuestring q{{s}}; bool found false; while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { string cur q.front(); q.pop(); if (isValid(cur)) { result.push_back(cur); found true; } if (found) continue; // 已找到最短解不再扩展 for (int j 0; j cur.size(); j) { if (cur[j] ! ( cur[j] ! )) continue; string next cur.substr(0, j) cur.substr(j 1); if (visited.insert(next).second) { q.push(next); } } } if (found) break; } return result.empty() ? vectorstring{} : result; } bool isValid(const string s) { int count 0; for (char c : s) { if (c () count; else if (c )) { if (--count 0) return false; } } return count 0; } };复杂度分析时间复杂度O(n × 2^P)最坏情况枚举所有删除组合空间复杂度O(2^P × n)队列和 visited 集合存储大量字符串两种方法对比方法时间复杂度空间复杂度推荐度DFS 剪枝O(2^P × n)O(n)⭐⭐⭐⭐⭐BFS 逐层删除O(n × 2^P)O(2^P × n)⭐⭐⭐BFS 的问题空间占用大需要存储大量中间字符串 。DFS 通过统计删除数量直接剪枝空间效率更高。总结要点说明核心思想统计多余括号 → DFS 尝试删/留 → 剪枝去重关键剪枝rightCount leftCount时返回去重方式HashSet存储结果时间复杂度O(2^P × n)P ≤ 20