301. Remove Invalid Parentheses

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        """tc O(2^N)   sc O(N)
        return all results => backtracking? (maintain current path valid)  + with minimun removal =how to determine valid? ==>  
        
        main idea:  generate unique answer exactly once (no rely on set)
                    to find out last removal position, we need to keep tracking last removal position and only remove ) 
                    for extra open parenthesis, (() ((), do same right -> left 
        """
        self.res = []
        
    #open_close :  ('(',')')
    """
    @last_open_i: position to start count 
    @last_close_j: position to start removing, remove position j range is [last_close_j,i] inclusive  
    
    """
        def remove(s,last_open_i,last_close_j,open,close): 
            cnt = 0
            for i in range(last_open_i,len(s)):
                if s[i] == open:
                    cnt += 1
                if s[i]== close:
                    cnt -= 1
                if cnt >= 0:
                    continue
                # cnt < 0 chose start pos to remove duplicate `close` 
                # stragtegy to avoid repeated removal is only remove 
                for j in range(last_close_j,i+1):
                    if s[j] == close and (j== last_close_j or s[j-1] != close):
                        #(1) new_string = s[:j]+s[j+1:]
                        #(2) last_open_i: next position to scan open should be i+1 in s but since we removed s[j] new open position of open to start should be i  
                        #(3) last_close_j is j, same logic as (2), hence we get j 
                        remove(s[:j]+s[j+1:len(s)],i,j,open,close)
                return #！！！ important： because after recursively removing invalid close parenthesis, we should not  continue any more because inner recursion has taken care of it 
            # assumiing for i loop there is no invalid parathesis. otherwise, we will not reach here since there is `return`
            rev = s[::-1]
            if open == '(': # left -> right end 
                remove(rev,0,0,')','(')  # here can replace with close,open but can't replace with  last_close_j,last_open_i
            else:
                self.res.append(rev) # finished right -> left 
        remove(s,0,0,'(',')') 
        return self.res