以实战为主，四个组合、四个排列、四个游戏及其他三个相关主题为例，给出回溯算法模板。 将深度优先探索烙印在大脑中，形成条件反射。
1 回溯简介
回溯算法，名字是骗人的，实际上是深度优先搜索(DFS )，通俗点说就是简单直接的暴力搜索方法(通过剪枝，会比暴力温柔一些。适用场景：序列确定(排列、组合、游戏(数独、n皇后等) ) ) ) ) ) )。
算法思想：本质上是DFS，但是有剪枝操作，一旦被确认为某种决策是不可能的，就不深入，不尝试所有的路径，而是追溯到上一步继续尝试。 尝试、失败、重试、直到成功，或者直到尝试完所有路径。 想象脑海里有一棵决策树
笔记本
其实人的一生不是决策树，每个人的人生轨迹都是一条路径。
要考哪个大学，要不要考研，要不要工作，如何选择offer，转行创业。
2 模板
通用模板为以下：求解回溯(n ) :
''''
DFS/BackTrack标准模板与通常的递归一样，遵循TUPR (结束、更新、向下钻取、复位)的类型
状态：
- path，choices是巴克特拉克()的参加
- other_state是一个外部Mutable变量
''''
ans=[]
other _ state=初始_ other _ state
深度跟踪(路径，选项) :
if len (路径)==n :------ -终端
ans.append (路径[ : ]
返回
第一季枚举(选项) :
IFIs _ good _ condition (路径、路径、其他状态) : # ---剪枝
更新状态((#----更新
回溯法(路径，选择法[ : I ]选择法) #-- -处理法
重置_其他_状态((#----重置
backtrack (初始路径，初始化_选择) ) ) ) ) ) )。) ) ) ) ) ) ) ) )。
返回和
如果只要找到路径就返回，则返回)可以返回bool变量。
如果找到路径，向下钻取并返回True，则返回trurn trues； 不进行r (复位)操作。 状态变量(包含历史上一系列决策的状态)如何保存？
输入backtrack ()函数：优点3:update_state )、reset_state ) )不需要代码，代码更紧凑(行数变少)的缺点3360状态变量很多请注意，如果条目过多，则可能会导致Mutable，从而导致牺牲一定空间效率的应用场景3360状态变量较少，占用内存的空间也较小。 Mutable/ImMutable都是backtrack ) )可以作为参与放在函数的外部，大多数mutable对象(例如Dict，Set，List ) ) 3360的优点)参与只能维持一个变量空间效率高的缺点：需要update_state ()和reset_state ) )的代码，代码行数多，应用场景：的状态变量太多，输入参数冗长，输入参数也输入例如，在八皇后中，注意列、Pie对角线、Na对角线的状态是n的倍数：如果不是Mutable，就不被报告
path (路径信息) :在当前状态下已经通过的路径。 这个路径是可行的(即快速剪枝)路径步骤数) :len ) path )，如果有path，除了每次不遍历path以外，还计算长度choices )候选列表在当前状态下的候选决策后期，可以删除： choices [ : I ] choices [ I 1: ]，排除已使用的选项。 例如，数组排除使用过的选择，保证与顺序无关地增加3360choices。 如(choices[I1:]所示，组合可以多次进行相同的选择，也可以与顺序无关地进行3360choices
2c4d56a01206716c9918ba?from=pc">3.1 组合
小结:
组合结果中的序列与顺序无关，[1, 2, 3]和[3, 2, 1]是同一个组合结果，所以需要对输入元素进行排序，确保结果不会重复后续选择:choices = choices[i+1:]: 限制使用次数为1choices = choices[i:]: 不限制使用次数技巧: 如果候选输入序列中有值重复的元素, 在钻入下一层backtrack()时，需要检验是否于之前的选择choice是否值相同, 如果相同，直接跳过，这样可以保证输出结果无重复。例子 leetcode 77, 常规的组合题, C(n, k)从n个元素选取k个出来, 正序排列，避免结果重复, 后续的选择是choices[i+1:]
例子 leetcode 39, 组合总和：不限制重复选取次数，正序排列，后续的选择是choices[i:]
例子 leetcode 40 组合总和ii:
组合：限制只能使用1次，正序排列，后续的选择是choices[i+1:]候选输入序列中有值重复的元素, 在钻入下一层backtrack()时，需要检验是否于之前的选择choice是否值相同, 如果相同，直接跳过，这样可以保证输出结果无重复。例子 leetcode 216 组合总和iii：
组合题目77和题目40的组合, 本质是C(n, k), 但要求和为target, 根据此剪枝即可3.2 排列
小结:
排列结果中的序列与顺序有关，[1, 2, 3]和[3, 2, 1]是两个排列结果，所以无需对输入元素进行排序后续选择: choices = choices[:i] + choices[i+1:] （剩余的元素）技巧: 无论排列还是组合，如果候选输入序列中有值重复的元素, 在钻入下一层backtrack()时，需要检验是否于之前的选择choice是否值相同, 如果相同，直接跳过，这样可以保证输出结果无重复。例子 leetcode 46: 经典全排列问题:
例子 leetcode 47: 输入元素重复，但输出要求无结果，有个技巧: 进行选择时, 第i步的选择不能是同一数字
例子 leetcode 60: 排列: 疯狂剪枝, 最后只剩一条路径
例子 leetcode 526: 排列: 增加了条件而已，按条件剪枝
3.3 棋类游戏
n皇后背景:
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。
n皇后的决策树: (以4为例)
例子 leetcode 51 n皇后: 返回所有的解决方案
状态记录第几个对角线是否可以放皇后: pie/na, 分别对应撇和捺两个方向的对角线。例子 leetcode 52: 返回所有的解决方案的个数
井字棋(Tic-Toc-Toe)背景:
两个玩家，一个打圈(◯)，一个打叉（✗），轮流在3乘3的格上打自己的符号，最先以横、直、斜连成一线则为胜。如果双方都下得正确无误，将得和局。
例子 leetcode 794 有效的井字游戏(Tic-Tac-Toe)
数独背景:
数独是一种数学逻辑游戏，游戏由9×9个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案。
例子: leetcode 37, 解数独, 游戏：数字依次放，序列决策问题，DFS
3.4 其他
例子: leetcode 17, 电话号码的字母组合, 第一个按键确定第二个按键的字母，依此类推，序列决策问题，显然用DFS
例子: leetcode 78, 组合：本质上是对每个元素进行是否选取的决策，总共有$2^n$种方法
例子: leetcode 22, 每个位置选取是放左括号、右括号，总共有$22n$种方法，但因为括号合法的限制，可以剪枝剪掉
4 总结
搜索的进阶路径：
枚举: 通过枚举所有可能的情况，简单粗暴地解决问题DFS搜索: 通过剪枝，可以跳过一些无效的状态，效率比枚举效率高一些。（剪枝：将不可能的路径，提前结束掉）启发策略: 可以进一步对状态空间中的每个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标，可省略大量无谓的搜索路径，提高效率。比如A*搜索，可以看下数独的例子，后续会有专题文章。