LeetCode 301. 删除无效的括号（DFS剪枝）

本文主要是介绍LeetCode 301. 删除无效的括号（DFS剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按任意顺序返回。

示例 1：

输入：s = “()())()”
输出：["(())()","()()()"]
示例 2：

输入：s = “(a)())()”
输出：["(a())()","(a)()()"]
示例 3：

输入：s = “)(”
输出：[""]

提示：

1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

思路：
一开始想通过状压枚举子集来写，但一算复杂度还不如dfs剪枝。
直接通过递归，枚举每一位要或者不要，策略如下：

统计出左括号数目减去右括号数据的大小，如果当前值小于0则剪枝
如果当前值不是括号，直接选择
记录合法结果的最大长度，如果当前长度加上后面所有的长度都小于这个最大值，则剪枝
如果当前左括号减去右括号数目大小，比剩下字符数还多，那么后面的全选右括号也不够了，剪枝
最终结果通过哈希去重

可以看到剪枝后的时间变化
在这里插入图片描述

class Solution {
public:void dfs(int id, string&s, string&now, int sum) {if(sum < 0) return;if(sum > s.size() - id) return;if(now.size() + s.size() - id < mx) return;if(id == s.size()) {if(mp[now]) return;mp[now] = true;if(sum != 0) return;if(now.size() > mx) {ans.clear();mx = now.size();ans.push_back(now);} else if(now.size() == mx) {ans.push_back(now);}return;}now.push_back(s[id]);int num = 0;if(s[id] == '(') num = 1;else if(s[id] == ')') num = -1;dfs(id + 1, s, now, sum + num);now.pop_back();if(num != 0) {dfs(id + 1, s, now, sum);}}vector<string> removeInvalidParentheses(string s) {string now;mx = 0;dfs(0, s, now, 0);return ans;}
private:int mx;vector<string>ans;unordered_map<string, bool>mp;
};