# Easy-understand 36ms c++ dfs

• ``````class Solution {
public:
string str;
int len;
map<string, vector<string> > all; // to store middle results

// the answer for string starting at index pos, with additional left brackets
vector<string> dfs(int pos, int left) {
string key = to_string(pos)+"-"+to_string(left);
if (all.find(key)!=all.end())
return all[key];

vector<string> ans, temp;
if (left<0 || pos==len) {
if (left==0) ans.push_back("");
return ans;
}

int newLeft=left; // by default, in case str[pos] is letter
if (str[pos]=='(') newLeft += 1; // in case we keep this '(', add one count of left brackets
else if (str[pos]==')') newLeft -= 1; // in case we keep this ')', minus one count of left brackets

for (auto& t : refine(dfs(pos+1, newLeft)))
ans.push_back(str[pos] + t);

if (str[pos]=='(' || str[pos]==')') // in case we remove '(' or ')', having the same num of left brackets
for (auto& t : refine(dfs(pos+1, left)))
ans.push_back(t);

all[key]=ans;
return ans;
}

vector<string> removeInvalidParentheses(string s) {
str = s;
len=str.length();
return refine(dfs(0, 0));
}

// helpers:
int max(int a, int b) {
return a>b ? a : b;
}

// keep strings with max length and remove duplicates
vector<string> refine(vector<string> vec) {
if (vec.empty())
return vec;

vector<string> temp;
int maxlen=-1;
for (auto& s : vec)
maxlen=max(maxlen, s.length());

set<string> seen;
for (auto& s : vec)
if (s.length()==maxlen && seen.find(s)==seen.end()) {
temp.push_back(s);
seen.insert(s);
}
return temp;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.