假设我们有一串括号。我们必须删除最少数量的无效括号并返回格式正确的括号字符串，因此，如果输入类似于“()（()()”，那么结果将是[“()()()”，“（ ）（()）”]
为了解决这个问题，我们将遵循以下步骤-
定义一个名为solve()的方法，它将接受pos、left、right、l、r、string array res和string temp。
如果pos与s的大小相同，则，
如果left等于0，right等于0，那么，
如果（m[temp]非零）为假，则，
res末端插入temp
m[temp]：=1
return
如果s[pos]与“（”相同且右>0，则，
调用solve（pos+1，left，right-1，l，r，res，temp+空字符串）
否则，当s[pos]与“）”相同且left>0时，则-
调用solve（pos+1，left-1，right，l，r，res，temp+空字符串）
如果s[pos]与“（”相同，则，
调用solve（pos+1，left，right，l+1，r，res，temp+“（”）
否则，当s[位置]与“）”相同且l>r时，则-
调用solve（pos+1，left，right，l，r+1，res，temp+'）
如果s[pos]不等于“（”，而s[pos]不等于“）”，则，
调用solve（pos+1，left，right，l，r，res，temp+s[pos]）
从主方法执行以下操作–
生成一个数组res
l:=0，r:=0
当i<0时，i的大小增加1
如果s[i]与“（”相同，则，
r增加1
否则，当s[i]与“）”相同时，则-
如果r非零，则将r减1
将else l增加1
调用函数solve(0,l,r,0,0,res)
返回res
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string s;
map <string ,int> m;
void solve(int pos, int left, int right,int l, int r, vector <string> &res, string temp=""){
if(pos == s.size()){
if(left==0 && right==0 && l==r){
if(!m[temp])
res.push_back(temp);
m[temp] = 1;
}
return;
}
if(s[pos] =='(' && right>0 ){
solve(pos+1,left,right-1,l,r,res,temp+"");
} else if(s[pos] ==')' && left>0) {
solve(pos+1,left-1,right,l,r,res,temp+"");
}
if(s[pos] =='(')solve(pos+1,left,right,l+1,r,res,temp+"(");
else if(s[pos] == ')' && l>r)solve(pos+1,left,right,l,r+1,res,temp+')');
if(s[pos]!='(' && s[pos]!=')')solve(pos+1,left,right,l,r,res,temp+s[pos]);
}
vector<string> removeInvalidParentheses(string s) {
vector <string > res;
int l = 0;
int r=0;
this->s = s;
for(int i =0;i<s.size();i++){
if(s[i] == '('){
r++;
} else if(s[i]==')') {
if(r)r--;
else l++;
}
}
solve(0,l,r,0,0,res);
return res;
}
};
main(){
Solution ob;
print_vector(ob.removeInvalidParentheses("()(()()"));
}“()(()()”
输出结果
[()()(), ()(()), ]