前言因为刚刚经历了秋天的把戏，总结起来，用手撕绳子的时候，遇到最多的是动态的计划和回溯。 我先写了对动态计划的理解，我还想总结一下回溯求解的方法和框架。 希望能帮到大家。 如果有错误的话请指出来
什么是回溯算法
回溯算法实际上是囊括所有可能性，从中寻找所有可行解的暴力检索算法。 回溯算法一般求解所有可行解。 在检索过程中发现不满足条件或找到一个可行解后，返回寻找其他可行解。 回溯算法的本质是包罗万象的，总体上效率不高，所以回溯算法一般只用于特定的问题
回溯算法的应用组合问题：给出具有n个整数的集合，其中包含k个数的所有组合排列问题：给出具有n个整数的集合，求出n个个数的所有排列方式子集问题：给出具有n个整数的集合，其所有子集的切断问题
回溯算法的本质——树问题
回溯算法的本质是在一棵树中进行决策，而不是用树这个数据结构来表示问题，在分析时回溯算法也满足树结构。 (78 .子集-力按钮(LeetCode ) (leetcode-cn.com) )以这个主题为例进行分析
3358www.Sina.com/:给出整数数组nums。 数组中的元素题目描述。 返回数组的所有可能子集(幂集)。 解集互不相同包含重复的子集。 您可以按不能返回编辑。 案例如下
3358 www.Sina.com/nums=[ 1，2，3 ] 3358 www.Sina.com/[ ]、[1]、[2]、[ 1，2 ]、[ 1，2 ]、[3]、[ 1，2 ]
放入集合的数量不同的话会成为不同的子集。 加入1、2、3中的任意一个都可以进行子集。 假设第一次放入的1，第二次可以在集合中放入2或3。 这又是假设在两种不同的情况下第二次放入的2，第三次3，3358 www.Sina.com/:画出来就能清楚地看到树。
如上图所示，回溯方法是在树下的阶层中不断探索，遇到结束条件时返回上面的阶层寻找该节点的其他子节点的方法。 因此，回溯方法本质是任意顺序全部可以用树结构分析的http://www.Sina.com/http://www.Sina.com /节点的结果(包括天空) http://w358 关于2，后面只考虑3，不考虑解决问题的模板。
如上所述，由于回溯算法都可以用树结构进行分析，所以也可以制作回溯法的固定解问题模板
首先，由于遍历树结构是递归的，所以当遇到终止节点时，需要“递归”，保存下一个搜索的结果if (终止条件) :并保存下一个搜索的结果return。 接下来，如上面的树形结构所示，每层都尽可能)将其称为包罗性。 因此，必须在一个级别内，即实际上在一个级别上递归地找到并处理所有可能取值的值。 例如，在上面的树结构中，对于空集合，选择1、2、3，分别处理for(each:所有可能的值) : pass，然后查看在循环中应该如何写。 假设取1 (处理1 ) )，则应该在1的下一层搜索)可以添加2或3 )；输入：:对1的处理结束后，是否应该“追溯”回去处理2和3。 因此，应该恢复原状，取消处理结果。 (那么，必须取消首先放入的1 ) for(each:所有可取值) :处理each self.backTracking )，检索下一层的恢复。 取消并合并处理结果的第一步骤：建立backTracking函数的参数和返回值的第二步骤：回溯(递归)输出：第三步骤)要在此层处理的所有可能值classion 参数) : if (终止条件) : #保存结果返回公式(each :所有可能的值) :过程检索下一层的恢复，然后返回处理结果例题的组合问题
分析:77 .工会-力量按钮(LeetCode ) ) (leetcode-cn.com) )。
33558www.Sina.com/:2:给定两个整数n和k，并返回范围[1，n]的所有可能
能的 k 个数的组合。可以按 任何顺序 返回答案 1 <= n <= 201 <= k <= n分析
这是求所有组合问题， 用回溯法来解。总结的回溯的方法如下确立backTracking函数的参数和返回值 参数 n作为遍历范围，k作为记录结果列表中数的个数startNum: 用于记录某一次遍历从哪一个开始， 因为是组合不能重复，所以我们只看后面的数（与上面的子集问题一样）temp: 暂时存放这一次搜索的结果返回值：无。 直接将到终止条件的保存进全局变量中确立终止条件： temp中的数到达k个时， 表明已从n个数中选出k个，即终止确立这一层处理的值： 因为只从上一层的数的后面中选择， 那么处理的值应该是从startNum开始到n的所有数字代码
注意：python中的列表都是引用传递（即无论在那里改变都会影响其他地方）， 所以再放入最终结果时， 应该进行深度拷贝copy.deepcopy(temp)
import copyclass Solution: def backTracking(self, n, k, startPos, temp): if len(temp) == k: self.res.append(copy.deepcopy(temp)) return for i in range(startPos, n + 1): temp.append(i) # 处理结果 self.backTracking(n, k, i + 1, temp) # 进行下一层的搜索 temp.pop() # 回溯结果， 删除放入result的内容 def combine(self, n, k): if k > n: raise ValueError("Invalid Input") if n < 1 or n > 20: raise ValueError("Out of Compass") self.res = [] self.backTracking(n, k, 1, []) return self.res今天算是解释了回溯， 并讲解了一道例题， 后面再放上其他例题。。。