# Remove Invalid Parentheses

#1

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses `(` and `)`.

Example 1:

```Input: "()())()"
Output: ["()()()", "(())()"]
```

Example 2:

```Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
```

Example 3:

```Input: ")("
Output: [""]
```

#2

The below algorithm uses a DFS approach to efficiently delete the invalid parentheses and add the result string to a list.

``````func removeInvalidParentheses(s string) []string {
result := make([]string, 0)
remove(s, &result,0, 0, []byte{'(', ')'})
return result
}

func remove(s string, result *[]string,start, lastRemovedIdx int, par []byte){
fmt.Println(s)
for stack,i:= 0, start;i<len(s);i++{
if s[i]==par[0] { stack++}
if s[i]==par[1]{ stack-- }
if stack>=0{continue}
for j:=lastRemovedIdx;j<=i;j++{
if(s[j]==par[1] && (j==lastRemovedIdx || s[j-1]!=par[1])){
remove(s[:j]+s[j+1:], result, i, j, par)
}
}
return
}
s = reverse(s)
if par[0]=='('{
remove(s, result, 0, 0, []byte{')', '('})
} else {
*result = append(*result, s)
}
}

func reverse(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
``````