"""
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
"""


def remove(s):
    results = _remove(s, 0, 0, '(', ')')
    return results


def _remove(s, i, j, open, close):
    ctr = 0
    while i < len(s) and ctr >= 0:
        ctr += 1 if s[i] == open else -1 if s[i] == close else 0
        i += 1

    first_j = j
    results = []
    while ctr < 0 and j < i:
        if s[j] == close and (j == first_j or s[j] != s[j - 1]):
            results.extend(_remove(s[0:j] + s[j + 1:], i - 1, j, open, close))
        j += 1

    s = s[::-1]
    if open == '(':
        results.extend(_remove(s, 0, 0, ')', '('))
    elif ctr == 0:
        results.append(s)
    return results


if __name__ == '__main__':
    print remove('(')
