```
class Solution(object):
def removeInvalidParentheses(self, s):
"""
:type s: str
:rtype: List[str]
"""
def dfs(s):
mi = calc(s)
if mi == 0:
return [s]
ans = []
for x in range(len(s)):
if s[x] in ('(', ')'):
ns = s[:x] + s[x+1:]
if ns not in visited and calc(ns) < mi:
visited.add(ns)
ans.extend(dfs(ns))
return ans
def calc(s):
a = b = 0
for c in s:
a += {'(' : 1, ')' : -1}.get(c, 0)
b += a < 0
a = max(a, 0)
return a + b
visited = set([s])
```