最近刷了几个回溯算法的主题，跟着labuladong刷，因为还很无知，没有找到规律，所以在这里总结一下。
1.回溯算法简介（这部分是参考这个博客）：
回溯思路的简单说明是将问题的解空间转换为图和树的结构表示，采用深度优先搜索策略进行遍历，在遍历过程中记录并寻找所有可行解和最优解。
回溯法的基本动作是搜索，在搜索过程中利用剪枝函数避免无效搜索。 有两种类型的剪枝函数。 1 .使用约束函数剪切不满足约束的路径。 2 .使用边界函数截断得不到最优解的路径。
问题的关键是如何定义问题的解空间并转换为树，即解空间树。 求解空间树有子集树和数组树两种。 两种算法的结构和思路大致相同。
1 )子集树：
给定的问题是，从n个要素的集合s中发现满足某一性质的部分集合时，对应的解空间为部分集合树。
0-1如背包问题，从给定重量、价值不同的物品中选出几种放入背包，在背包满足不重的情况下，使背包内物品的价值最大化。 其解空间是典型的子集树。
回溯法搜索子集树的算法范式如下。
voidbacktrack(intt ) if (TN ) output(x ) x； ELSEfor(intI=0； i=1； I ) { x[t]=i； if(constraint(t ) bound(t ) t ) ) backtrack ) t1； )2)林荫道：
给定的问题是，在决定n个要素满足某一性质的数组时，对应的解空间是数组树。
就像旅游销售员的问题一样，要求一个销售员一次在几个城市旅行，步行的路程最小。 其解是几个城市的排列，解空间是排列树。
回溯搜索数组树的算法范式如下：
voidbacktrack(intt ) if (TN ) output(x ) x； elsefor(intI=t； i=n； I ) swap(x[t]，x[i]； if(constraint(t ) bound(t ) t ) ) backtrack ) t1； swap(x[t]，x[i]； } } 2.回溯算法的框架
需要考虑的三个步骤
3358 www.Sina.com/http://www.Sina.com/:也就是说，已经选择了。
1）:也就是说，你现在可以做出的选择。
路径即到达决策树底部，无法进一步选择的条件。
result=[]def backtrack (路径，选择列表) : if退出条件： result.add (路径)路径) return for选择输入选择列表：选择backtrack (路径，选择列表)
绘制递归树，找到状态变量(回溯函数的参数)这一步骤非常重要
根据题意，确立终止条件
查找选择列表(与函数参数相关)，并与第一步密切相关
判断是否需要修剪树枝
选择并递归调用，进入下一个层次
取消选择
作者： show-me-the-code-2
链接： https://leet code-cn.com/problems/subsets/solution/c-zong-Jie-Liao-hui-su-Wen-ti-lei-xing-dang
资料来源：力扣)。
版权归作者所有。 商业转载请联系作者取得许可。 非商业转载请注明出处。
2）选择列表
3）结束条件
for选择输入选择列表： #从进行选择的选择列表中删除路径. add (选择)后退路径，取消选择列表) #选择列表3.排列相关问题
1）全排列：
首先找到递归树，不需要结束条件，直接添加到结果中即可。 选择是加入节点后的数字，所以有start。
4.子集相关问题
如果与前一个相比存在重复，则需要修剪树枝并重新排列数组。 如果上一个与当前数量相同，它将被剪枝。
1）子集1
2）子集2
与子集类似，但因为可以重复选择，所以start不使用1。
backtrack(nums，path，I，sum nums[i]，target )； //I和更新当前状态的sum 5.组合相关问题
判断条件是数组的长度，如果不能重复选择，start需要1。
1）组合总和
因为不能重复，所以start加1。
2）组合
知道不求答案是一个抛硬币问题，可以用动态规划的方法进行。
3）组合总和2
1 )后台的参数是什么？
参数与路径、选择、选择相关联的是开始参数、目标(与边界相关联) )
2 )最后返回的res，怎么写才能返回，局部变量，全局变量？
res不作为参数使用，具体是这样操作
RES=[]defbacktrack(XX，XX ) : xxxx backtrack (xx ) return res 3)何时需要修剪分枝？
如果有重复，就需要修剪树枝。 如果要确定前几个和后几个是否相同，请直接通过