最近在leetcode上面做过算法问题，但是已经遇到了两个回溯算法的问题，感觉一点想法也没有，所以决定总结一下java如何实现回溯算法
什么是回溯算法
(摘自百度百科() )。
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试的过程中寻找问题的解，如果发现不满足求解条件，则“回溯”返回尝试另一条路径。 回溯法是一种选优搜索法，为了达成目标，在选优条件下向前搜索。 但是，在探索了某一步的时候，如果原来的选择不优秀或者没有达到目标，就返回一步重新选择。 这样，如果不顺利就返回的技术是回溯法，将满足有回溯条件的状态的点称为“回溯点”。 许多复杂、规模大的问题都使用回溯法，有“通用求解方法”的美称。
(摘自别人的博客) ) ) ) )。
在包含问题所有解的解空间树中，遵循深度优先搜索的策略，从根节点开始搜索深度搜索解空间树。 当搜索到某个节点时，首先判断该节点是否包含问题的解，如果包含，则从该节点开始继续搜索，如果不包含，则向祖先的节点追溯。 (实际上，回溯法是指对隐式图的深度优先搜索算法。)。 用回溯法求问题的所有解时，要追溯到根，搜索根节点的所有可能执行的子树并结束。 另一方面，用回溯法求任一个解时，只要找到问题的一个解就结束。
使用回溯算法
追溯到现在，我认为是一种递归。 有以下4个参数。 当然不一定是我举例的类型。 因主题而异
全局变量集合存储满足条件的所有答案。 示例： List list
集合中将保存满足条件的答案。 示例： ListtempList
给定算法问题的输入条件。 这可能是字符串，也可能是数组
附加参数(有无因主题而异) )。
举个例子
import java.util.ArrayList；
import java.util.List；
public class Permutations {
//主题描述： givenacollectionofdistinctintegers，return all possible permutations.()给出一组不同的整数并返回所有可能的组合) )
publiclistpermute(int[]nums ) {
//保存所有集合的全局变量
List list=new ArrayList (；
//传递了三个参数，没有其他参数
acktrack(list，new ArrayList )，nums )；
返回列表；
}
privatevoidbacktrack(listlist，List tempList，int [] nums ) {
//满足一个结束条件，即条件时
templist.size (==nums.length ) )。
//向全局变量添加满足条件的集合
list.add(newArraylist ) templist )；
} else{
for(intI=0； i nums.length； I ) {
templist.contains (nums [ I ] ) continue；
如果tempList中不包含nums[i]，则添加
templist.add(nums[I]；
//递归调用，此时的tempList在满足结束条件之前持续变化
backtrack(list，tempList，nums )；
system.out.println('templist内容：'templist'----'I的值：' i )；
通过删除tempList的最后一个元素，返回上次调用时的数据。 也就是说，我想返回上一个节点，重新搜索满足条件的内容。 只有这样才能实现后退
templist.remove(templist.size ) (- 1 )；
}
}
}
publicstaticvoidmain (字符串[ ] args ) {
int [ ] nums={ 1，2，3 }；
(new Permutations () ).permute ) nums；
}
}
main方法测试，输出语句的结果如下，可以观察回溯的过程
tempList的内容： [ 1，2，3 ]---- I的值：2
tempList的内容： [ 1，2 ]---- I的值：1
tempList的内容： [ 1，3，2 ]---- I的值：1
tempList的内容： [ 1，3 ]---- I的值：2
tempList的内容：[1]----I的值：0
tempList的内容： [ 2，1，3 ]---- I的值：2
tempList的内容： [ 2，1 ]---- I的值：0
tempList的内容： [ 2，3，1 ]---- I的值：0
tempList的内容： [ 2，3 ]---- I的值：2
tempList的内容：[2]-------i的值：1
tempList的内容： [ 3，1，2 ]---- I的值：1
tempList的内容： [ 3，1 ]---- I的值：0
tempList的内容： [ 3，2，1 ]---- I的值：0
tempList的内容： [ 3，2 ]---- I的值：1
tempList的内容：[3]----I的值：2
我理解了这个主题，是从这个for循环的i=0开始继续递归，持续删除集合的最末尾的元素，追溯到完成为止。 这样，就产生了第一元素为1的各种各样的状况。 这样，然后for循环i=1开始，产生顶元素为2的各个情况。
图像点是指一个根节点具有1、2、3三个元素，首先从1出发，查找满足最低条件的节点，然后返回上一个节点查找满足条件的节点，直到返回1，返回1后从2开始