要搞懂最后一行代码首先要明白什么是递归，递归分为递和归两部分，递就是往下传递，归就是往回走。递归你从什么中央调用最终还会回到什么中央去，我们来画个复杂的图看一下
这是一棵十分复杂的3叉树，假设要对他停止DFS遍历，当沿着1→2这条途径走下去的时分，list中应该是[1，2]。由于是递归调用最终还会回到节点1，假设不把2给移除掉，当沿着1→4这个分支走下去的时分就变成[1，2，4]，但实践上1→4这个分支的结果应该是[1，4]，这是由于我们把前一个分支的值给带过去了。当1，2这两个节点遍历完之后最终还是前往节点1，在回到节点1的时分就应该把结点2的值给移除掉，让list变为[1]，然后再沿着1→4这个分支走下去，结果就是[1，4]。
我们来总结一下回溯算法的代码模板吧
private void backtrack("原始参数") {
//终止条件(递归必需要有终止条件)
if ("终止条件") {
//一些逻辑操作（可有可无，视状况而定）
return;
} for (int i = "for循环末尾的参数"; i < "for循环完毕的参数"; i++) {
//一些逻辑操作（可有可无，视状况而定）
//做出选择
//递归
backtrack("新的参数");
//一些逻辑操作（可有可无，视状况而定）
//撤销选择
}
}
有了模板，回溯算法的代码就十分容易写了，下面就依据模板来写几个经典回溯案例的答案。
八皇后成绩
八皇后成绩也是一道十分经典的回溯算法题，前面也有对八皇后成绩的专门引见，有不明白的可以先看下394，经典的八皇后成绩和N皇后成绩。他就是不断的尝试，假设以后位置能放皇后就放，不断到最后一行假设也能放就表示成功了，假设某一个位置不能放，就回到上一步重新尝试。比如我们先在第1行第1列放一个皇后，如下图所示
然后第2行从第1列末尾在不抵触的位置再放一个皇后，然后第3行……不断这样放下去，假设能放到第8行还不抵触阐明成功了，假设没到第8行的时分出现了抵触就回到上一步继续查找适宜的位置……来看下代码
//row表示的是第几行
public void solve(char[][] chess, int row) {
//终止条件，row是从0末尾的，最后一行都可以放，阐明成功了 if (row == chess.length) { //本人写的一个公共办法，打印二维数组的， //主要用于测试数据用的 Util.printTwoCharArrays(chess); System.out.println(); return; } for (int col = 0; col < chess.length; col++) {
//验证以后位置能否可以放皇后
if (valid(chess, row, col)) {
//假设在以后位置放一个皇后不抵触，
//就在以后位置放一个皇后
chess[row][col] = 'Q';
//递归，在下一行继续……
solve(chess, row + 1);
//撤销以后位置的皇后
chess[row][col] = '.';
}
}
}
全陈列成绩
给定一个没有反双数字的序列，前往其一切能够的全陈列。
示例:
输入: [1,2,3]
输入:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这道题我们可以把它当做一棵3叉树，所以每一步都会有3种选择，详细进程就不在剖析了，直接依据下面的模板来写下代码
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), nums);
return list;
(责任编辑：admin)