回溯法 java,简述回溯法的算法步骤
回溯算法
定义
回溯算法实际上是基于类似DFS(深度优先搜索)枚举的搜索尝试过程，主要是在搜索尝试过程中寻求问题的解。如果发现解条件不满足，它会“回溯”回之前的状态，尝试另一条路径。满足回溯条件的效果好的点称为“回溯点”。
追踪相关问题
DFS和回溯算法的区别
DFS在一个方向上不断搜索，直到到达底部，回溯算法基于DFS。不同的是，在搜索过程中，满足退出条件后，恢复状态，返回上一级，再次进行搜索。所以回溯算法和DFS的区别在于有无无状态重置。
什么时候用回溯算法？
当遇到问题的不成功路径时，需要“后退”，这样才能找到所有的解，所以可以使用回溯算法。即当满足结束条件或找到错误路径时，取消选择，回到之前的状态，继续尝试，直到找到所有解。
回溯算法的基本步骤
找到状态变量(回溯函数的参数)
根据问题的含义定义递归终止条件
找标准选择列表(与函数的自变量相关)，与第一步紧密相关。
判断该分支是否需要修剪，即预先排除不合格路径。
并选择递归调用，然后进入下一级。
取消选择
回溯算法有哪些类型？
子集，组合问题
序列问题
搜索，n皇后类问题，
:子集，请注意数组与元素的顺序有关，与组合的顺序无关。比如，[1，2]和[2，1]是同一个组合(子集)，但是[1，2]和[2，1]是两个不同的数组。
回溯算法的通用模板
结果=[]
定义回溯(路径，选择列表):
如果满足结束条件：
Result.add(路径)
返回
在选择列表中选择：
做出选择
Back(路径，选择列表))。
取消选择
主题示例
Leetcode78。子集
问题的描述
给定一组没有重复元素的整数数组num，将返回该数组所有可能的子集(幂集)。
注意：解决方案集不能包含重复的子集。
样品
输入：nums=[1，2，3]
输出：
[
[3]、
[1],
[2]、
[ 1,2,3 ],
[ 1,3 ],
[ 2,3 ],
[ 1,2 ],
[]
]
Python代码问题
对于应用上述回溯算法的模板，path表示选择的路径，而对于i in range(start，len[nums]]表示当前可用的列表元素。请注意，之前选择的元素不能在复合类问题中选择。因为有重复的结果，所以需要start参数来控制每个循环中的可选元素[start，leet]。
类别解决方案：
defsubsets(self，nums: List[int] )-list[int]):
定义回溯(nums，path，start):
添加res结果的路径
res.append(path.copy))
#当前可选参数列表
forIinrange(start，Len ) nums)):
#选择
path.append(nums[I])).
回溯(NUMS，路径，i 1).
#取消选择
path.pop(
res=[]
回溯(nums，[，0 ]).
返回结果
Leetcode77。组
问题的描述
给定两个整数n和k，1中所有可能的k组合。返回n个。
样品
输入：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从开始增加
forIinrange(start，n 1):
#选择
track.append(I).
Back (n，k，i 1，track))。
#取消选择
轨道.流行(
res=[]
track=[]
Back (n，k，1，track))。
返回结果
通过以上的讲解，读者应该对回溯算法的概念和模板的类型有了基本的了解。回溯的关键是选择和取消选择的过程。相信读者会有很好的体验，一定会得到。将持续更新回溯算法相关问题的解决方案，请持续关注！
如果你喜欢作者，欢迎你喜欢，收藏，关注。谢谢你。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。