题目
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")(" 输出：[""]
解题
方法一：dfs暴搜
class Solution { public: unordered_set<string> set;//得用set去重，搜出来的结果可能会重复 string s; int maxNum;//'('或')'数量最多为maxNum，用于剪枝 int pathLen;//当前path长度 int n;//s长度 void dfs(int idx,string path,int score){ if(score<0||score>maxNum) return; if(idx==n){ if(score==0&&path.size()>=pathLen){ if(path.size()>pathLen) set.clear(); pathLen=path.size(); set.insert(path); } return; } char c=s[idx]; if(c=='('){ dfs(idx+1,path+c,score+1); dfs(idx+1,path,score); } else if(c==')'){ dfs(idx+1,path+c,score-1); dfs(idx+1,path,score); } else dfs(idx+1,path+c,score); } vector<string> removeInvalidParentheses(string s) { this->s=s; n=s.size(); int l=0,r=0; for(char c:s){ if(c=='(') l++; else if(c==')') r++; } maxNum=min(l,r); dfs(0,"",0); return vector<string>(set.begin(),set.end()); } };
