Leetcode 31. 删除无效的括号

心路历程：

一开始看到有点懵，后来发现有点像按照一定规则穷举所有可能情况，想到了排列组合问题，再结合问题长度不固定，无法用已知个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 Counterpath = []res = []n = len(s)kuohaos = ['(', ')']mystack = Mystack()maxlen = 0def dfs(i):  # i代表遍历字符串的第i个元素# nonlocal s, n, res, path, mystack # 这一行可有可无nonlocal maxlen  # 这一行必须有# 剪枝：把一些不可能更长的去掉;if (n - len(path)) + len(''.join(path)) < maxlen:returnif i == n:string = ''.join(path.copy())maxlen = max(maxlen, len(string))res.append(string)returnif 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 dequeself.sk = deque()def pop(self, ele):if ele == '(':self.sk.pop()elif ele == ')':self.sk.append('(')else:assert False, eledef append(self, ele):if ele == '(':self.sk.append('(')elif ele == ')':assert len(self.sk) != 0self.sk.pop()else:assert False, eledef len(self):return len(self.sk)