# Straight Forward Solution with Explanation

• ) is always follow (, so we just need to count the unmatched (.

Three situations in each turn:

1. (, pick and not pick it.
2. ), if we have unmatched (, 2 choices, else drop it.
3. pick other chars.

Since it need to remove the minimum brackets, we should figure out the maximum matched ().
Notice the order of below two lines:

``````dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);
``````

It ensures the maximum result appear before the shorter ones.

``````/**
* @param {string} s
* @return {string[]}
*/
var removeInvalidParentheses = function(s) {
var res = [], max = 0;
dfs(s, "", 0, 0);
return res.length !== 0 ? res : [""];

function dfs(str, subRes, countLeft, maxLeft){
if(str === ""){
if(countLeft === 0 && subRes !== ""){
if(maxLeft > max)
max = maxLeft;
if(max === maxLeft && res.indexOf(subRes) === -1)
res.push(subRes);
}
return;
}
if(str[0] === '('){
dfs(str.substring(1), subRes + '(', countLeft + 1, maxLeft + 1);
dfs(str.substring(1), subRes, countLeft, maxLeft);
}else if(str[0] === ')'){
if(countLeft > 0)
dfs(str.substring(1), subRes + ')', countLeft - 1, maxLeft);
dfs(str.substring(1), subRes, countLeft, maxLeft);
}else{
dfs(str.substring(1), subRes + str[0], countLeft, maxLeft);
}
}
};``````

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