class Solution {
public:int len=0;int max_score=0;unordered_set<string> hash;int n=0;vector<string> removeInvalidParentheses(string s) {int l=0, r=0;// l代表需要删除的左括号数量，r代表需要删除的右括号数量n = s.size();int right=0,left=0;// 为了剪枝，合理的字符串中最多出现多少个左括号for(char c:s){if(c=='('){l++;left++;}else if(c==')'){if(l!=0) l--;else r++;right++;}}len = n - l - r;// 删除掉不合法的括号后，最后字符串的长度max_score = min(left,right);dfs(s,"",0,0,l,r);return {hash.begin(),hash.end()};}void dfs(string s, string res, int score, int index, int l, int r){if(res.size()==len&&score==0){hash.insert(res);return;}if(index==n) return;if(score<0||score>max_score) return; //剪枝一if(l<0||r<0) return; //剪枝二char c = s[index];if(c=='('){dfs(s, res+c, score+1, index+1, l, r);dfs(s, res, score, index+1, l-1, r);}else if(c==')'){dfs(s, res+c, score-1, index+1, l, r);dfs(s, res, score, index+1, l, r-1);}else{dfs(s, res+c, score, index+1, l, r);}}
};