回溯法（backtracking）是暴力搜索法中的一种。实际上他是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时就回溯返回，尝试别的路径。当路径满足求解条件时，就继续往下搜索，直到找到最终需要的结果为止。其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就退一步，继续尝试 …… ，在经典的教科书中，八皇后问题就是使用回溯法解决的，还有常见的解数独以及全排列等等。
回溯和递归的区别
递归一般关注的是结果，只需要返回最终结果就行，而回溯一般更倾向于过程，有时候还需要记录访问的路径。回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，对已知错误的结果没必要在枚举下去了。
回溯算法的使用
对于回溯算法我们可以把它当做一棵 n 叉树的前序遍历，树的每个节点最多有 n 个子节点，如下图所示。因为回溯需要使用递归，递归在往下走的时候选择当前节点，往回走的时候撤销选择。
我们用一个最常见的例子-全排列，来看下回溯算法的使用。给定一个没有重复字母的字符串 s ，找到该字符串的所有排列。
Input:S = ABC
Output: ABC ACB BAC BCA CAB CBA
我们看到上面排列中每个位置有 3 种字母可选择，分别是 A,B,C 。并且字母不能重复选择，也就是说不能出现类似于 [A,A,A] 这样的排列。因为出现多种选择，也就是有多种不同的分支，所以我们很容易把它想象成为一棵树。树中每个节点最多有 n 个子节点，如下图所示，这里 n 是数组的长度，选择的时候如果出现重复的字母，我们就把他剪掉。
我们看到每个节点的值可以从数组中任选一个，但不能重复选择。这里所有从根节点到叶子节点路径上字母的集合就是要求的结果，那么这个结果该怎么求呢？我们使用一个集合来记录从根节点到当前节点访问过的所有节点值，具体逻辑就是如果递归往下走的时候把当前节点添加到集合中，当递归往回走的时候在把当前节点从集合中移除，如下图所示，因为字母不能重复选择，所以这里把不能选择的分支给移除了，圆圈中的数字表示访问的顺序。
来看下代码：
public List<List<Character>> permutation(char[] chars) {
List<List<Character>> res = new ArrayList<>();// 返回结果的集合。
backtrack(res, chars, new boolean[chars.length], new ArrayList<>());
return res;
}
// 回溯算法。
private void backtrack(List<List<Character>> list, char[] chars,
boolean[] visited, List<Character> pathList) {
// 递归的终止条件，如果字母都被使用完了，说明没有字母可选择。
if (pathList.size() == chars.length) {
// 因为list是引用传递，这里必须要重新new一个。
list.add(new ArrayList<>(pathList));
return;
}
// 这里可以把它看做是遍历n叉树每个节点的子节点。
for (int i = 0; i < chars.length; i++) {
// 因为不能重复选择，如果选择过了就直接跳过，相当于剪枝。
if (visited[i])
continue;
// 选择当前元素，并标记为已选择。
pathList.add(chars[i]);
visited[i] = true;
// 递归，到下一层。
backtrack(list, chars, visited, pathList);
// 往回走的时候撤销选择，把最后一次添加的元素给移除。
pathList.remove(pathList.size() - 1);
// 移除之后相当于没有选择，注意这里还要标记为最初的状态。
visited[i] = false;
}
}
对于上面的代码我们来总结一下。
private void backtrack("原始参数") {
// 终止条件(因为回溯需要使用递归，而递归必须要有终止条件)
if ("终止条件") {
// 一些逻辑操作，通常是保存结果的（可有可无，视情况而定）。
return;
}
// 一些逻辑操作，（可有可无，视情况而定）。
// 这里把它看做一棵树，需要遍历每个节点的子节点，所以这里使用for循环。
for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
// 一些逻辑操作，或者是剪枝，可以剪掉无效的分支（可有可无，视情况而定）。
// 递归往下走，做出选择。
// 递归
backtrack("新的参数");
// 递归往回走，要撤销选择。
// 一些逻辑操作（可有可无，视情况而定）。
}
}
这个就是回溯算法比较常用的模板，根据这个模板，我们可以解决大多数经典回溯算法题。
