# Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return *a list of ***unique strings*** that are valid with the minimum number of removals*. You may return the answer in **any order**.

```
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)
```

There are many different approaches to this problem but backtracking feels the most natural in my opinion.

## Related Problems

Given an object, return a valid JSON string of that object. You may assume the object only inludes strings, integers, arrays, objects, booleans, and null. The returned string should not include extra spaces. The order of keys should be the same as the order returned by Object.keys().

Please solve it without using the built-in JSON.stringify method.

The Hamming Distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return *the ***Hamming distance*** between them*.

Write an algorithm to determine if a number n is happy.

A **happy number** is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it **loops endlessly in a cycle** which does not include 1.

Those numbers for which this process **ends in 1** are happy.

Return true *if* n *is a happy number, and* false *if not*.

Given a string num that contains only digits and an integer target, return **all possibilities*** to insert the binary operators *'+'*, *'-'*, and/or *'*'* between the digits of *num* so that the resultant expression evaluates to the *target* value*.

Note that operands in the returned expressions **should not** contain leading zeros.