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;
}
}
```