删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()" 输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()" 输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
暴力搜索yyds：
class Solution {
public:
vector<string> ans;
map<string, int> m;
int n, k = -1, flag = 0;;
string s1;
void dfs(int index, string ss, int sum, int cnt){
if(index == n){
if((k == - 1 || cnt == k) && sum == 0){
if(flag == 0){
flag = 1;
k = cnt;
}
if(m[ss] != 1){
ans.push_back(ss);
m[ss] = 1;
}
}
return;
}
if(s1[index] == ')'){
if(sum > 0){
dfs(index + 1, ss + s1[index], sum - 1, cnt + 1);
dfs(index + 1, ss, sum, cnt);
}else{
dfs(index + 1, ss, sum, cnt);
}
}else if(s1[index] == '('){
dfs(index + 1, ss + s1[index], sum + 1, cnt + 1);
dfs(index + 1, ss, sum, cnt);
}else{
dfs(index + 1, ss + s1[index], sum, cnt);
}
}
vector<string> removeInvalidParentheses(string s) {
s1 = s;
n = s.size();
dfs(0, "", 0, 0);
return ans;
}
};