LC 93 · 复原 IP 地址思路分割问题回溯枚举切割点多了合法性判断。和131分割回文串框架一样区别是终止条件变成切出了4段且用完所有字符每段的合法性判断有三条不能有前导零、值不能超过255、段不能为空。剪枝已经切出4段但字符还没用完直接返回剩余字符明显不够或太多也可以提前剪。边界条件比较多细心列清楚。LC 78 · 子集思路收集回溯树上每一个节点的结果而不是只收叶子。组合和分割题是在叶子节点收集答案子集题是每进入一层递归就收集一次——空集、单元素、两元素……直到全集全部都要。框架几乎不变就是把result.append(path[:])从终止条件里挪到递归开头其他照旧。LC 90 · 子集 II思路78 40 的结合子集收集方式 树层去重。数组有重复元素先排序在同一层遇到和前一个相同的元素跳过i start and nums[i] nums[i-1]和40的去重逻辑完全一致。收集方式和78一样每层都收。做完39/40/78/90这四题组合和子集的套路基本摸透了。回溯三类问题现在凑齐了两类组合/分割收叶子和子集收所有节点明天排列登场是第三类区别在于排列有序、不用startIndex但要used数组去重。回溯树的形状不一样感受一下区别。明天继续
（补档）算法复健 Day20 - 回溯 LC 93，78，90
LC 93 · 复原 IP 地址思路分割问题回溯枚举切割点多了合法性判断。和131分割回文串框架一样区别是终止条件变成切出了4段且用完所有字符每段的合法性判断有三条不能有前导零、值不能超过255、段不能为空。剪枝已经切出4段但字符还没用完直接返回剩余字符明显不够或太多也可以提前剪。边界条件比较多细心列清楚。LC 78 · 子集思路收集回溯树上每一个节点的结果而不是只收叶子。组合和分割题是在叶子节点收集答案子集题是每进入一层递归就收集一次——空集、单元素、两元素……直到全集全部都要。框架几乎不变就是把result.append(path[:])从终止条件里挪到递归开头其他照旧。LC 90 · 子集 II思路78 40 的结合子集收集方式 树层去重。数组有重复元素先排序在同一层遇到和前一个相同的元素跳过i start and nums[i] nums[i-1]和40的去重逻辑完全一致。收集方式和78一样每层都收。做完39/40/78/90这四题组合和子集的套路基本摸透了。回溯三类问题现在凑齐了两类组合/分割收叶子和子集收所有节点明天排列登场是第三类区别在于排列有序、不用startIndex但要used数组去重。回溯树的形状不一样感受一下区别。明天继续
