The basic idea is recursive DFS with pruning function.

Generate new strings by removing parenthesis, and calculate the total number of mismatched parentheses inside the string by *function* **calc(s)**.

If the mismatched parentheses increased, then discard the string.

```
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])
return dfs(s)
```

ref: http://bookshadow.com/weblog/2015/11/05/leetcode-remove-invalid-parentheses/