回溯算法
定义
回溯算法实际上基于类似DFS (深度优先搜索)枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，如果发现不满足求解条件，则“回溯”返回前一状态，尝试另一条路径，效果良好满足有回溯条件的状态的点称为“回溯点”。
追溯相关问题
DFS与回溯算法的区别
DFS一直在一个方向搜索，直到到达最底层，而回溯算法是基于DFS的。 不同的是，在搜索过程中，在满足退出条件后，恢复状态，回到上一层，再次进行搜索。 因此，回溯算法和DFS的区别在于有无无状态复位。
什么时候使用回溯算法
当遇到问题不成功的路径时，需要“后退”，从而找到所有的解时，使用回溯算法。 也就是说，满足结束条件或发现不是正确的路径时，取消选择，返回到之前的状态，继续尝试直到找到所有的解。
回溯算法的基本步骤
找到状态变量(回溯函数的参数)
基于题意定义递归终止条件
寻找标准选择列表(与函数自变量相关)，并与第一步密切相关
判断是否需要修剪树枝，即，事先排除不符合条件路径
选择并递归调用，然后前进到下一个层次
取消选择
回溯算法类的题型有哪些
子集，组合类问题
序列问题
搜索，n皇后类问题、
:子集，请注意数组与元素的顺序有关，而与组合的顺序无关。 例如，[ 1，2 ]和[ 2，1 ]是同一组合(子集)，但[ 1，2 ]和[ 2，1 ]是两种不同的阵列。
回溯算法的通用模板
result=[]
def backtrack (路径，选择列表) :
if满足结束条件：
result.add (路径)
返回
for选择in选择列表：
做出选择
后退(路径，选择列表) )。
取消选择
主题示例
Leetcode78 .子集
问题的说明
给定一组不含重复元素的整数数组nums，将返回该数组的所有可能子集(幂集)。
说明：解集不能包含重复的子集。
样品
输入： nums=[ 1，2，3 ]
输出：
[
[3]、
[1]，
[2]、
[ 1，2，3 ]，
[ 1，3 ]，
[ 2，3 ]，
[ 1，2 ]，
[]
]
python代码问题
应用了上述回溯算法的模板，path表示选定路径，for i in range(start，len[nums]] )表示当前可用的列表元素。 请注意，在组合类问题中无法选择以前选择的元素。 由于存在重复结果，因此需要start参数来控制每个循环中可选择的元素[start，leet]
类解决方案：
defsubsets(self，nums: List[int] )-list[int] ) :
defbacktrack(nums，path，start ) :
将path添加到res结果
res.append(path.copy ) )
#当前可选择的参数列表
forIinrange(start，Len ) nums ) ) :
#选择
path.append(nums[I] ) ) )。
backtrack(NUMS，path，i 1 ) )。
#取消选择
path.pop (
res=[]
backtrack(nums，[，0 ] ) )。
返回结果
Leetcode77 .组
问题的说明
给定两个整数n和k，则返回1 . n中所有可能的k个组合。
样品
输入： n=4，k=2
输出：
[
[ 2，4 ]，
[ 3，4 ]，
[ 2，3 ]，
[ 1，2 ]，
[ 1，3 ]，
[ 1，4 ]，
]
python代码问题
正题与前题基本相同，都是组合类问题，只是递归结束条件不同，正题的结束条件是路径长为k时len[track]==k，将结果追加到res中。
应用上述回溯算法模板时，track表示选定路径，forIinrange(start，n 1 )表示当前可用的列表元素。 请注意，start必须从1开始，表示可以为主题选择的数量为1.n。
类解决方案：
defcombine(self，n: int，k: int )-list[int] ) :
数字选择范围为1-n
defbacktrack(n，k，start，track ) :
iflen(track )==k:
res.append(track.copy ) )
返回
#注意I从start开始增加
forIinrange(start，n 1 ) :
#选择
track.append(I )。
后退(n，k，i 1，track ) )。
#取消选择
track.pop (
res=[]
track=[]
后退(n，k，1，track ) )。
返回结果
通过以上说明，读者应该对回溯算法的概念和模板的类型有基本的认识，回溯的关键是选择和取消选择的过程，相信读者会好好体验，一定会获得。 将继续更新回溯算法的相关问题解，请继续关注！
如果你喜欢作者，欢迎点赞、收藏和关注。 谢谢你。