class Solution:
    def isValid(self, str):
        stack = []
        for c in str:
            if c=='(':
                stack.append('(')
            elif c==')':
                if stack:
                    stack.pop()
                else:
                    return False
        return not stack
    def removeInvalidParentheses(self, s: str) -> List[str]:
        if self.isValid(s):
            return [s]
        #Auto remove duplicate
        result = set()
        #Remove one cases
        for i in range(len(s)):
            removeds = s[:i]
            if len(s)>1:
                removeds += s[i+1:]
            if self.isValid(removeds):
                result.add(removeds)
        if result:
            return list(result)
        #Remove two cases
        for j in range(len(s)):
            removeds = s[:j]
            if len(s)>1:
                removeds += s[j+1:]
            for i in range(len(removeds)):
                tmp = removeds[:i]
                if len(removeds)>1:
                    tmp += removeds[i+1:]
                if self.isValid(tmp):
                    result.add(tmp)
        if result:
            return list(result)
        #Remove three cases
        for k in range(len(s)):
            removeds1 = s[:k]
            if len(s)>1:
                removeds1 += s[k+1:]
            for j in range(len(removeds1)):
                removeds2 = removeds1[:j]
                if len(removeds1)>1:
                    removeds2 += removeds1[j+1:]
                for i in range(len(removeds2)):
                    tmp = removeds2[:i]
                    if len(removeds2)>1:
                        tmp += removeds2[i+1:]
                    if self.isValid(tmp):
                        result.add(tmp)
        if result:
            return list(result)
        #Remove four cases
        for l in range(len(s)):
            removeds1 = s[:l]
            if len(s)>1:
                removeds1 += s[l+1:]
            for k in range(len(removeds1)):
                removeds2 = removeds1[:k]
                if len(removeds1)>1:
                    removeds2 += removeds1[k+1:]
                for j in range(len(removeds2)):
                    removeds3 = removeds2[:j]
                    if len(removeds2)>1:
                        removeds3 += removeds2[j+1:]
                    for i in range(len(removeds3)):
                        tmp = removeds3[:i]
                        if len(removeds3)>1:
                            tmp += removeds3[i+1:]
                        if self.isValid(tmp):
                            result.add(tmp)
        return list(result)