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

碎碎念

整理了两个不同视角的回溯模版，对解排列组合问题非常有用。
核心：从递归树遍历、选择与撤销的视角看回溯算法，可能比较抽象，做几道题就有感觉了

模版：

枚举型回溯：枚举选哪个，适合解枚举遍历型问题

本质是逐坑位看可以填哪些元素（坑位为主体对象）

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_idx+1,新pfl)撤销选择（回退his）

实战leetcode：46、17、22、79、51

选择型回溯：当前元素选与不选，适合解组合型问题

本质是逐元素填坑位（元素为主体对象），即看在每个时间点当前元素选还是不选。并且规定当前时间点不选，后续都不会选（因为后续选，当前不选的情况可以转换成当前选后续不选，因此仅保留当前选后续不选的case即可）

n=len(nums)ans=[]# 保存所有可能的答案his=[]# 之前被选择的元素构成的历史记录# idx不是用来表示时间步的，而是表示【元素索引】，然后看该元素选或者不选defdfs(idx):# 表示已遍历完所有元素，可以输出组合了ifidx==n:ans.append(his的备份版)return# 满足提前跳出条件if满足提前跳出条件:return# 不选 nums[idx]，# 并且表示后续也都不会选（idx+1 跳到下一个元素了）dfs(idx+1)# 选 nums[idx]his.append(nums[idx])# 选择# 这里idx不一定要加1，不加1，表示下一轮继续可以选元素 nums[idx]# 加1 则表示后续不会选 nums[idx]了dfs(idx+1)his.pop()# 撤销选择

实战leetcode：78、39、131

Leetcode Hot100 里的回溯相关题目及解法提示

55.全排列 46：不可重复枚举元素，用一个 sel_list 保存被选过的元素下标
56.子集 78：选与不选最经典场景
57.电话号码的字母组合 17：不重复枚举数字对应的字母，建立数字到可选字母的映射元组
58.组合总数 39：选与不选，注意不选则后续永远不会选的逻辑，并且注意递归出口为剩余差值<=0
59.括号生成 22：可重复枚举括号，用 dfs(num_left,num_right) 表示当前状态，配合剪枝看当前可行列表
60.单词搜索 79：可重复枚举，ans = [False] # 用列表初始化，不用单变量ans=False, 注意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 列已被皇后占用，反之未被占用

斜线占用原理：比如y=x+b，表示某条斜线，那么任意斜线上的点（ x 0 , y 0 ） （x_0,y_0）（x0​,y0​）满足y 0 − x 0 = b y_0-x_0=by0​−x0​=b，因此可以通过diag[x 0 − y 0 x_0-y_0x0​−y0​]=True，将某个斜线的占用情况置为True

参考：link