# 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s 由小写英文字母以及括号 '(' 和 ')' 组成s 中至多含 20 个括号
## template
```python
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
left, right = 0, 0
for c in s:
if c == "(":
left += 1
elif c == ")":
if left == 0:
right += 1
else:
left -= 1
else:
pass
def is_valid(s):
level = 0
for c in s:
if c == "(":
level += 1
elif c == ")":
if level == 0:
return False
else:
level -= 1
else:
pass
return level == 0
def dfs(s, index, left, right, res):
"""
from index to find ( or ),
left and right means how many ( and ) to remove
"""
if (left == 0) and (right == 0) and is_valid(s):
res.append(s)
return
for i in range(index, len(s)):
c = s[i]
if c in ["(", ")"]:
if (i > 0) and (c == s[i - 1]):
continue
if (c == ")") and (right > 0):
dfs(s[:i] + s[i + 1 :], i, left, right - 1, res)
elif (c == "(") and (left > 0):
dfs(s[:i] + s[i + 1 :], i, left - 1, right, res)
else:
pass
res = []
dfs(s, 0, left, right, res)
return list(set(res))
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```