回溯模版及实战（待完善）

碎碎念整理了两个不同视角的回溯模版对解排列组合问题非常有用。核心从递归树遍历、选择与撤销的视角看回溯算法可能比较抽象做几道题就有感觉了模版枚举型回溯枚举选哪个适合解枚举遍历型问题本质是逐坑位看可以填哪些元素坑位为主体对象ans[]his[]# 这里的 path_idx用来表示【坑位索引】# pfl Potentially Feasible List (PFL)潜在可行列表defdfs(path_idx,pfl):ifpath_idx 满足保存条件:# 使用备份版是因为append保存的是索引# 后续改动his内部元素会影响当前探索的结果ans.append(his的备份版)ifpath_idx 达到最大深度return# 有时PFL可能为空此时提前结束当前层遍历而返回上一层递归for选择inpfl:if选择 满足剪枝条件continue做选择更新历史 和 pfl dfs(path_idx1,新pfl)撤销选择回退his实战leetcode46、17、22、79、51选择型回溯当前元素选与不选适合解组合型问题本质是逐元素填坑位元素为主体对象即看在每个时间点当前元素选还是不选。并且规定当前时间点不选后续都不会选因为后续选当前不选的情况可以转换成当前选后续不选因此仅保留当前选后续不选的case即可nlen(nums)ans[]# 保存所有可能的答案his[]# 之前被选择的元素构成的历史记录# idx不是用来表示时间步的而是表示【元素索引】然后看该元素选或者不选defdfs(idx):# 表示已遍历完所有元素可以输出组合了ifidxn:ans.append(his的备份版)return# 满足提前跳出条件if满足提前跳出条件:return# 不选 nums[idx]# 并且表示后续也都不会选idx1 跳到下一个元素了dfs(idx1)# 选 nums[idx]his.append(nums[idx])# 选择# 这里idx不一定要加1不加1表示下一轮继续可以选元素 nums[idx]# 加1 则表示后续不会选 nums[idx]了dfs(idx1)his.pop()# 撤销选择实战leetcode78、39、131Leetcode Hot100 里的回溯相关题目及解法提示55.全排列 46不可重复枚举元素用一个 sel_list 保存被选过的元素下标56.子集 78选与不选最经典场景57.电话号码的字母组合 17不重复枚举数字对应的字母建立数字到可选字母的映射元组58.组合总数 39选与不选注意不选则后续永远不会选的逻辑并且注意递归出口为剩余差值059.括号生成 22可重复枚举括号用 dfs(num_left,num_right) 表示当前状态配合剪枝看当前可行列表60.单词搜索 79可重复枚举ans [False] # 用列表初始化不用单变量ansFalse, 注意pfl的变化以及剪枝61.分割回文串 131选或不选思路见下前n-1个分割点索引右边为分割点选或者不选第n个点必选。配合剪枝判断子串是否回文 用dfs(idx, last)构造递归idx为当前分割点索引last表示上一个被选择的分割点索引62.N皇后 51不可重复枚举O(1)实现剪枝看左右斜线和上方有没有放置皇后具体用三个辅助列表实现用两个列表表示所有的斜线可能 diag1[False]*(2*n-1)diag2[False]*(2*n-1)col[c]true 表示第 c 列已被皇后占用反之未被占用斜线占用原理比如yxb表示某条斜线那么任意斜线上的点 x 0 , y 0 x_0,y_0x0​,y0​满足y 0 − x 0 b y_0-x_0by0​−x0​b因此可以通过diag[x 0 − y 0 x_0-y_0x0​−y0​]True将某个斜线的占用情况置为True参考link