心路历程：

一开始看到有点懵，后来发现有点像按照一定规则穷举所有可能情况，想到了排列组合问题，再结合问题长度不固定，无法用已知个for循环表示，从而想到了回溯。这个题相当于需要在一定规则下枚举。
按照回溯的模板，递归循环是整个字符串s，for循环是候选集合。候选集合为第i个元素 “选” 或者 “不选” ，按照这个思路，其实就已经可以把所有可能组成的情况给遍历到，然后再从所有结果里搜集满足条件的即可。

这道题在回溯问题里很有代表性，考察了很多点，包括怎么对排列问题进行建模（选or不选）、如何判断满足括号条件（栈）、如何剪枝。一开始把问题想简单了，导致写完之后花了很长时间解决未通过的案例，这里面还是有一些细节需要考虑的，比如任何回溯都得在递归函数调用结束后“恢复现场”。

注意的点：

1、回溯算法在记录path时一定要记得copy
2、回溯函数中任何递归调用后都得恢复路径，比如这个问题里遇到字母时，虽然形成的树只有一个分支，但是返回后也得恢复path才行；当时第一次想这个问题以为单分支不用恢复路径导致de了半天bug。还是需要理解回溯是遍历边这个概念。
3、剪枝的判断直接返回就行，把剪枝的部分当作不需要记录path的终止条件即可。
4、每个节点候选集合都有空字符串和括号两个选择，需要遍历，没法贪婪地认为有括号选括号，因为需要考虑所有的组合。
5、注意题目中找的是删除最少括号后的所有可能组合，也就是最长的合法解，并且不能包含重复元素。

感悟：

1、算法题主要考察两类能力：一是对问题进行建模的能力；二是逻辑条件的想全能力。很多时候知道问题大概怎么做，但是具体想各种情况时还是会漏掉一些情况或者想错一些情况。
2、回溯问题debug可以从打印路径和候选集合的角度寻找错误。
3、很多算法中循环的建模思路都可以按照’选‘or’不选‘ 或者 ’选哪个‘的思路考虑，尤其在回溯、递归、动态规划等问题上，可以建模为决策问题。这一点其实和DRL在求解组合优化问题时的两类动作建模思路是一致的。

解法：

这道题有两个思路：思路一：剪枝+选择后序有可能形成最长路径；解法二：剪枝+找到所有的+判断满足条件的最长的。第二个可能更清晰，不过由于刚做完括号的题所以按照第一个思路写的AC解：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        from collections import Counter
        path = []
        res = []
        n = len(s)
        kuohaos = ['(', ')']
        mystack = Mystack()
        maxlen = 0

        def dfs(i):  # i代表遍历字符串的第i个元素
            # nonlocal s, n, res, path, mystack # 这一行可有可无
            nonlocal maxlen  # 这一行必须有

            # 剪枝：把一些不可能更长的去掉;
            if (n - len(path)) + len(''.join(path)) < maxlen:
                return
           
            if i == n:
                string = ''.join(path.copy())
                maxlen = max(maxlen, len(string))
                res.append(string)
                return
            
            if s[i] not in kuohaos:
                path.append(s[i])
                dfs(i+1)
                path.pop()  # 这块也得回溯！！！！！！！
            else:
                candidate = [""]
                # 看第i个括号能不能选即可
                if s[i] == '(':  # 后面）的数量大于等于栈长+1就可以选
                    c = Counter(s[i+1:] + ')')  # +1防止为空
                    # print(mystack.sk, c[')'], mystack.len())
                    if c[')'] - 1 >= mystack.len() + 1: 
                        candidate.append("(")
                elif s[i] == ')':  # 栈里有左括号
                    if mystack.len() > 0:
                        candidate.append(')')
                else:
                    assert False, s[i]
                for each in candidate:
                    # print(each, path, i)
                    path.append(each)  # path 怎么会这么长？
                    # 维护一下栈
                    if each != "":
                        mystack.append(each)
                    dfs(i+1)
                    path.pop()
                    if each != "":
                        mystack.pop(each)
        dfs(0)
        # 返回res里最长的
        lengths = [len(eve) for eve in res]
        res = [eve for eve in res if len(eve) == max(lengths)]
        return list(set(res))  # 需要去重
                        

class Mystack:
    def __init__(self):
        from collections import deque
        self.sk = deque()
    
    def pop(self, ele):
        if ele == '(':
            self.sk.pop()
        elif ele == ')':
            self.sk.append('(')
        else:
            assert False, ele
    
    def append(self, ele):
        if ele == '(':
            self.sk.append('(')
        elif ele == ')':
            assert len(self.sk) != 0
            self.sk.pop()
        else:
            assert False, ele

    def len(self):
        return len(self.sk)