对于深度优先遍历DFS，通过上一篇《详说广度优先搜索BFS的用法》中提到的DFS的遍历的顺序，不难看出：这个算法会尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。
提到回溯算法，还是会想到深度优先搜索DFS，在我看来在树的深度优先遍历算法（dfs）中，回溯指的就是树遍历的状态重置，和含有递归结构。
对于回溯算法的应用有很多：排列、组合、子集相关问题，我们来通过一些算法应用来更快掌握：
应用一：排列
解题思路：
要求返回其所有可能的全排列，先确定第一个数字，之后再往后确定，可以将这个过程看做是一个树的形成过程，整过过程也就是一个树深度优先遍历的思想，也就是回溯。其中还用到了递归。排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），我们需要记录哪些数字已经使用过，因此声明一个boolean类型数组，当值为true时，意味着该数字已经使用过；确定回溯方法的参数：给定的数组，最后返回的列表，遍历存放的列表(会被重置，重置之前内容加入到要返回的列表)，给定的数组的长度，遍历元素的位置，判断是否被选择的boolean类型的数组（标记当前状态）确定递归终止条件：一个排列中的数字已经选够了 ，我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth，表示当前要确定的是某个全排列中下标为 depth的那个数是多少；
class Solution {
public List> permute(int[] nums) {
//回溯参数
List> res = new ArrayList<>();
List path = new ArrayList<>();
int len = nums.length;
boolean [] used = false;
if(nums==0){
return res;
}
dfs(nums,res,path,len,0,used[]);
return res;
}
//回溯函数
dfs(int[]nums,List> res,List path,int len,int depth,boolean[] used){
if(depth == len){
// 变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
// 在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址。
// 这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到空的列表对象。
// 解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
res.add(new ArrayList<>(path));
return;
}
for(int i=0;i
应用二：组合
解题思路：
首先能够脑构出构造树，清楚整个回溯流程；
根据示例 1：输入: candidates = [2, 3, 6, 7]，target = 7。候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。基于以上的想法，可以画出如下构造树
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，为了排除掉重复的，我们在每一次搜索的时候设置 下一轮搜索的起点 begin。
思考回溯函数的参数。
确定递归终止条件：要找的数的组合 中数小于等于0时，结束此次递归。
class Solution {
public List> combinationSum(int[] candidates, int target) {
List> res = new ArrayList<>();
List path = new ArrayList<>();
int len = candidates.length;
// boolean[] used = new boolean[len];
dfs(candidates,res,path,target,0,len);
return res;
}
private void dfs(int[] candidates, List> res,List path,int target,int begin,int len){
if(target<0){
return;
}
if(target == 0){
res.add(new ArrayList<>(path));
return;
}
for(int i=begin;i
总结一下广度优先遍历/搜索应用的步骤：
第一步：明确递归参数第二步：明确递归终止条件第三步：明确递归函数中的内容第四步：明确回溯返回值
如果这篇文章对你有帮助的话，就留下一个赞吧！
