- Scan from left to right, make sure count["("]>=count[")"].
- Then scan from right to left, make sure count["("]<=count[")"].

```
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
removed = 0
results = {s}
count = {"(": 0, ")": 0}
for i, c in enumerate(s):
if c == ")" and count["("] == count[")"]:
new_results = set()
while results:
result = results.pop()
for j in range(i - removed + 1):
if result[j] == ")":
new_results.add(result[:j] + result[j + 1:])
results = new_results
removed += 1
else:
if c in count:
count[c] += 1
count = {"(": 0, ")": 0}
i = len(s)
ll = len(s) - removed
for ii in range(ll - 1, -1, -1):
i-=1
c = s[i]
if c == "(" and count["("] == count[")"]:
new_results = set()
while results:
result = results.pop()
for j in range(ii, ll):
if result[j] == "(":
new_results.add(result[:j] + result[j + 1:])
results = new_results
ll -= 1
else:
if c in count:
count[c] += 1
return list(results)
```