# C++: 3ms DFS without generating duplicates. Maybe easy to understand?

• This problem can be solved via DFS (backtracking) approach. A challenge will be the duplicate of valid parentheses being generated. For example, given string `"())"`, removal of either the first or second `')'` yields the same result. This problem arises when there are continuous `'('`s or `')'`s. To eliminate such duplicates, we can store the results into an unordered_set.

We can also eliminate such duplicates when handling continuous `'('` and `')'`s. How? Suppose there are n continuous `'('`s starting at position `pos`. Among these n`'('`s, the number of `'('`s being kept could be 0, 1, ..., n, which corresponds to the number of removals n, n-1, ... , 0. Then we go to position `pos+n` directly by traversing all these (n+1) possibilities. For example, for string `"(a(()))"`, suppose the intermediate result is `"(a"` when we meet two consecutive `'('`s. We then deliver 3 intermediate results `"(a"`, `"(a("`, and `"(a(("` to position 4, respectively. This approach will avoid duplicates.

The mechanism of avoiding duplicates is not obvious as it looks like. Suppose we have `"~~~))*))"`, where `'*'` represents a char rather than `')'`, and `'~'` any characters. During DFS, if we do not keep `'*'`, then keeping `"))"` before `'*'` and removing `"))"` after `'*'` is equivalent to removing it after `'*'` while keeping it after. If so, the uniqueness of the results using this approach would fail. However, this case doesn't hold:

• If `'*'` is not a parenthesis, we can't remove it. `"))*''` and `"*))"` are not identical.
• If `'*'` is `')'`, we can exclude it from intermediate result during DFS. The results may contain `"))"`, either before or after `'('`. However, these two solutions are not optimal: why not we keep the `"))"` before `'('` and at the same time keeping `'('` itself and a single `')'` after that, in order to avoid removing this pair?

The main function is as follows. We first calculate how many `'('` and `')'` will be removed when using minimum removal. The results are stored into `lrem` and `rrem` (l and r indicates direction of bracket, left or right. And rem represents remaining.) During DFS, these two variables indicate how many removal operations could be conducted.

``````    vector<string> removeInvalidParentheses(string s) {
string path;
vector<string> res;
int lrem = 0;
int rrem = 0;
for(auto c : s) {
if(c == '(')
lrem ++;
else if(c == ')') {
if(lrem > 0)
lrem --;
else
rrem ++;
}
}
helper(s, 0, path, res, 0, lrem, rrem);

return res;
}
``````

The DFS helper function is as follows. When we meet a `'('` or a `')'`, we count the number of its continuous occurrence. `k-1` is the last occurrence. `nLeft` is the number of `'('`s that are unpaired till now.

``````    void helper(string& s, int pos, string& path, vector<string>& res, int nLeft, int lrem, int rrem) {
if(nLeft > s.length() - pos || lrem < 0 || rrem < 0 || nLeft < 0) // [pos, n - 1] can provide n - pos ')'s
return;
if(pos >= s.length()) {
res.push_back(path);
return;
}
const string path_init(path);
if(s[pos] != ')' && s[pos] != '(') { // Just keep it.
path += s[pos];
helper(s, pos + 1, path, res, nLeft, lrem, rrem);
path.pop_back();
}
else if(s[pos] == '(') {
int k = pos + 1;
while(k < s.length() && s[k] == '(') {
k ++;
}

for(int i = 0; i <= k - pos; i ++) { // i: number of '(' being kept
//(k-pos-i) - number of removals from (k-pos) '('s
helper(s, k, path, res, nLeft + i, lrem - (k-pos-i), rrem);  // keep '('
path.push_back(s[pos]);
}
path = path_init;
}
else {
int k = pos + 1;
while(k < s.length() && s[k] == ')') {
k ++;
}

for(int i = 0; i <= k - pos; i ++) { // i: number of ')' being kept
//(k-pos-i) - number of removals from (k-pos) ')'s
helper(s, k, path, res, nLeft - i, lrem, rrem - (k-pos-i));  // keep '('
path.push_back(s[pos]);
}
path = path_init;
}
}
``````

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