什么叫回溯算法
对于回溯算法的定义，百度百科上是这样形容的：回溯算法 实际上一个相似 枚举 的搜寻尝试过程，次要是在搜寻尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的门路 。回溯法是一种选优搜寻法，按选优条件向前搜寻，以达到目标。 但当摸索到某一步时，发现原先抉择并不优或达不到指标，就退回一步从新抉择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多简单的，规模较大的问题都能够应用回溯法，有“通用解题办法”的美称。
看明确没，回溯算法其实就是一个一直摸索尝试的过程，摸索胜利了也就胜利了，摸索失败了就在退一步，持续尝试……，
组合总和
组合总和算是一道比拟经典的回溯算法题，其中有一道题是这样的。
找出所有相加之和为 n 的 k 个数的组合。组合中只容许含有 1 – 9 的正整数，并且每种组合中不存在反复的数字。
阐明：
- 所有数字都是正整数。
- 解集不能蕴含反复的组合。
示例 1:
输出 : k = 3, n = 7
输入: [[1,2,4]]
示例 2:
输出 : k = 3, n = 9
输入: [[1,2,6], [1,3,5], [2,3,4]]
这题说的很明确，就是 从 1 - 9 中选出 k 个数字，他们的和等于 n，并且这 k 个数字不能有反复的 。所以第一次抉择的时候能够从这 9 个数字中任选一个，沿着这个分支走上来，第二次抉择的时候还能够从这 9 个数字中任选一个，但因为不能有反复的，所以要排除第一次抉择的，第二次抉择的时候只能从剩下的 8 个数字当选一个……。这个抉择的过程就比拟清朗了，咱们能够把它看做一棵 9 叉树，除叶子结点外每个节点都有 9 个子节点，也就是上面这样
从 9 个数字中任选一个，就是沿着他的任一个分支始终走上来，其实就是 DFS（如果不懂 DFS 的能够看下 373，数据结构 -6, 树），二叉树的 DFS 代码是上面这样的
public static void treeDFS(TreeNode root) {if (root == null)
return;
System.out.println(root.val);
treeDFS(root.left);
treeDFS(root.right);
}这里能够仿照二叉树的 DFS 来写一下 9 叉树，9 叉树的 DFS 就是通过递归遍历他的 9 个子节点，代码如下
public static void treeDFS(TreeNode root) {
// 递归必须要有终止条件
if (root == null)
return;
System.out.println(root.val);
// 通过循环，别离遍历 9 个子树
for (int i = 1; i <= 9; i++) {
//2，一些操作，可有可无，视状况而定
treeDFS("第 i 个子节点");
//3，一些操作，可有可无，视状况而定
}
}DFS 其实就相当于遍历他的所有分支，就是列出他所有的可能后果，只有判断后果等于 n 就是咱们要找的，那么这棵 9 叉树最多有多少层呢，因为有 k 个数字，所以最多只能有 k 层。来看下代码
public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), k, 1, n);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
// 终止条件，如果满足这个条件，再往下找也没什么意义了
if (list.size() == k || n <= 0) {
// 如果找到一组适合的就把他退出到汇合 list 中
if (list.size() == k && n == 0)
res.add(new ArrayList<>(list));
return;
}
// 通过循环，别离遍历 9 个子树
for (int i = start; i <= 9; i++) {
// 抉择以后值
list.add(i);
// 递归
dfs(res, list, k, i + 1, n - i);
// 撤销抉择
list.remove(list.size() - 1);
}
}代码相对来说还是比较简单的，咱们来剖析下（如果看懂了能够间接跳过）。
1，代码 dfs 中最开始的中央是终止条件的判断，之前在 426，什么是递归，通过这篇文章，让你彻底搞懂递归中讲过，递归必须要有终止条件。
2，上面的 for 循环别离遍历他的 9 个子节点，留神这里的 i 是从 start 开始的，所以有可能还没有 9 个子树，后面说过，如果从 9 个数字中抉择一个之后，第 2 次就只能从剩下的 8 个抉择了，第 3 次就只能从剩下的 7 个中抉择了……
3，在第 20 行 dsf 中的 start 是 i +1，这里要说一下为什么是 i +1。比方我抉择了 3，下次就应该从 4 开始抉择，如果不加 1，下次还从 3 开始就呈现了数字反复，显著与题中的要求不符
4，for 循环的 i 为什么不能每次都从 1 开始，如果每次都从 1 开始就会呈现后果反复，比方抉择了[1，2]，下次可能就会抉择[2，1]。
5，如果对回溯算法不懂的，可能最不容易了解的就是最初一行，为什么要撤销抉择。如果常常看我公众号的同学可能晓得，也就是我常常提到的分支净化问题，因为 list 是援用传递，当从一个分支跳到另一个分支的时候，如果不把前一个分支的数据给移除掉，那么 list 就会把前一个分支的数据带到下一个分支去，造成后果谬误（上面会讲）。那么除了把前一个分支的数据给移除以外还有一种形式就是每个分支都创立一个 list，这样每个分支都是一个新的 list，都不相互烦扰，也就是上面图中这样
代码如下
public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), k, 1, n);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
// 终止条件，如果满足这个条件，再往下找也没什么意义了
if (list.size() == k || n <= 0) {
// 如果找到一组适合的就把他退出到汇合 list 中
if (list.size() == k && n == 0)
res.add(new ArrayList<>(list));
return;
}
// 通过循环，别离遍历 9 个子树
for (int i = start; i <= 9; i++) {
// 创立一个新的 list，和原来的 list 撇清关系，对以后 list 的批改并不会影响到之前的 list
List<Integer> subList = new LinkedList<>(list);
subList.add(i);
// 递归
dfs(res, subList, k, i + 1, n - i);
// 留神这里没有撤销的操作，因为是在一个新的 list 中的批改，原来的 list 并没有批改，// 所以不须要撤销操作
}
}咱们看到最初并没有撤销的操作，这是因为每个分支都是一个新的 list，你对以后分支的批改并不会影响到其余分支，所以并不需要撤销操作。
留神：大家尽量不要写这样的代码，这种形式尽管也能解决，但每个分支都会从新创立 list，效率很差。
要搞懂最初一行代码首先要明确什么是递归，递归分为递和归两局部，递就是往下传递，归就是往回走。递归你从什么中央调用最终还会回到什么中央去，咱们来画个简略的图看一下
这是一棵非常简单的 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;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
// 终止条件
if (tempList.size() == nums.length) {
// 阐明找到一一组组合
list.add(new ArrayList<>(tempList));
return;
}
for (int i = 0; i < nums.length; i++) {
// 因为不能有反复的，所以有反复的就不能选
if (tempList.contains(nums[i]))
continue;
// 抉择以后值
tempList.add(nums[i]);
// 递归
backtrack(list, tempList, nums);
// 撤销抉择
tempList.remove(tempList.size() - 1);
}
}是不是感觉很简略。
子集问题
给定一组不含反复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
阐明：解集不能蕴含反复的子集。
示例:
输出: nums = [1,2,3]
输入:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
咱们还是依据模板来批改吧
`public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> list = new ArrayList<>();
// 先排序
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
// 留神这里没有写终止条件，不是说递归肯定要有终止条件的吗，这里怎么没写，其实这里的终止条件
// 隐含在 for 循环中了，当然咱们也能够写 if(start>nums.length) rerurn; 只不过这里省略了。list.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
// 做出抉择
tempList.add(nums[i]);
// 递归
backtrack(list, tempList, nums, i + 1);
// 撤销抉择
tempList.remove(tempList.size() - 1);
}
}所以相似这种题基本上也就是这个套路，就是先做出抉择，而后递归，最初再撤销抉择。在讲第一道示例的时候提到过撤销的起因是避免把前一个分支的后果带到下一个分支造成后果谬误。不过他们不同的是，一个是终止条件的判断，还一个就是 for 循环的起始值，这些都要具体问题具体分析。上面再来看最初一到题解数独。
解数独
数独大家都玩过吧，他的规定是这样的
一个数独的解法需遵循如下规定：
- 数字 1-9 在每一行只能呈现一次。
- 数字 1-9 在每一列只能呈现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。
过程就不在剖析了，间接看代码，代码中也有具体的正文，这篇讲的是回溯算法，这里次要看一下 backTrace 办法即可，其余的能够先不必看
`// 回溯算法
public static boolean solveSudoku(char[][] board) {return backTrace(board, 0, 0);
}
// 留神这里的参数，row 示意第几行，col 示意第几列。private static boolean backTrace(char[][] board, int row, int col) {
// 留神 row 是从 0 开始的，当 row 等于 board.length 的时候示意数独的
// 最初一行全副读遍历完了，阐明数独中的值是无效的，间接返回 true
if (row == board.length)
return true;
// 如果以后行的最初一列也遍历完了，就从下一行的第一列开始。这里的遍历
// 程序是从第 1 行的第 1 列始终到最初一列，而后第二行的第一列始终到最初
// 一列，而后第三行的……
if (col == board.length)
return backTrace(board, row + 1, 0);
// 如果以后地位曾经有数字了，就不能再填了，间接到这一行的下一列
if (board[row][col] != '.')
return backTrace(board, row, col + 1);
// 如果下面条件都不满足，咱们就从 1 到 9 中抉择一个适合的数字填入到数独中
for (char i = '1'; i <= '9'; i++) {// 判断以后地位 [row，col] 是否能够放数字 i，如果不能放再判断下
// 一个能不能放，直到找到能放的为止，如果从 1 - 9 都不能放，就会上面
// 间接 return false
if (!isValid(board, row, col, i))
continue;
// 如果能放数字 i，就把数字 i 放进去
board[row][col] = i;
// 如果胜利就间接返回，不须要再尝试了
if (backTrace(board, row, col))
return true;
// 否则就撤销从新抉择
board[row][col] = '.';
}
// 如果以后地位 [row，col] 不能放任何数字，间接返回 false
return false;
}
// 验证以后地位 [row，col] 是否能够寄存字符 c
private static boolean isValid(char[][] board, int row, int col, char c) {for (int i = 0; i < 9; i++) {if (board[i][col] != '.' && board[i][col] == c)
return false;
if (board[row][i] != '.' && board[row][i] == c)
return false;
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
}
return true;
}总结
回溯算法要和递归联合起来就很好了解了，递归分为两局部，第一局部是先往下传递，第二局部达到终止条件的时候而后再反弹往回走 ，咱们来看一下阶乘的递归
其实回溯算法就是在往下传递的时候把某个值给扭转，而后往回反弹的时候再把原来的值还原即可。比方八皇后的时候咱们先假如一个地位能够放皇后，如果走不通就把以后地位给撤销，放其余的地位。如果是组合之类的问题，往下传递的时候咱们把以后值退出到 list 中，而后往回反弹的时候在把它从 list 中给移除掉即可。