LeetCode 301. 删除无效的括号（回溯）

示例 1:
输入: "()())()"
输出: ["()()()", "(())()"]

示例 2:
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例 3:
输入: ")("
输出: [""]

class Solution {
	unordered_set<string> ans;//去重
	int mindel = INT_MAX;
public:
    vector<string> removeInvalidParentheses(string s) {
    	int l = 0, r = 0, del = 0;
    	string t;
    	dfs(s,0,t,l,r,del);
    	return vector<string>(ans.begin(), ans.end());
    }

    void dfs(string& s, int idx, string t, int l, int r, int del)
    {
    	if(del > mindel)//删的多了，没意义了
    		return;
    	if(idx == s.size())
    	{
    		if(l==r && del < mindel)//左右括号数量要一样多
    		{
    			mindel = del;
    			ans.clear();
    			ans.insert(t);
    		}
    		else if(l==r && del == mindel)
    			ans.insert(t);
    		return;
    	}
    	if(s[idx]!='(' && s[idx]!=')')//不是括号，加上，跳过
    		return dfs(s, idx+1, t+s[idx], l, r, del);
    	if(s[idx]=='(') l++;
    	else if(s[idx] == ')') r++;
    	if(l >= r)//左括号在过程中一直>=右括号
    		dfs(s, idx+1, t+s[idx], l, r, del);//不删除
    	if(s[idx]=='(') l--;//回溯
    	else if(s[idx] == ')') r--;//回溯
    	if(l >= r)
    		dfs(s, idx+1,t, l, r, del+1);//删除
    }
};