回溯算法是一种常用的算法，本文会以详细介绍回溯算法的基本思想及其代码实现例子@mikechen
回溯算法定义
回溯算法，是一种选优搜索法，又称为试探法，按选优条件向前搜索以达到目标。
回溯算法简要说：但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法基本思想
回溯法实际上也是一种试错的思路，通过不断尝试解的组合来达到求解可行解和最优解的目的。
回溯算法的基本思路，主要分为如下4步：
1）定义一个解空间，它包含问题的解；
2）利用适于搜索的方法组织解空间；
3）利用深度优先法搜索解空间；
4）利用限界函数避免移动到不可能产生解的子空间。
回溯算法模板框架
分析完过程，回溯算法模板框架如下：
private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作（可有可无，视情况而定）
return;
}
for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
//一些逻辑操作（可有可无，视情况而定）
//做出选择
//递归
backtrack("新的参数");
//一些逻辑操作（可有可无，视情况而定）
//撤销选择
}
}
看明白了么，回溯算法：其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就在退一步，继续尝试。
回溯算法应用场景
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合；
- 排列问题：N个数按一定规则全排列，有几种排列方式；
- 切割问题：一个字符串按一定规则有几种切割方式；
- 子集问题：一个N个数的集合里有多少符合条件的子集；
- 棋盘问题：N皇后，解数独等等。
回溯算法经典例子
1.N皇后问题
1）题目
这个是一个比较经典的问题， 意思是将N个“皇后”放在N*N的棋盘上，每个皇后不能再同一列，同一行和斜对角。
如下图所示：
2）思路
把这个问题划分成8个阶段，依次将8个棋子放到第一行、第二行、第三行……第八行， 放置过程中不停地检查当前方法，是否满足要求。
- 满足 跳到下一行继续放置棋子；
- 不满足 换种方法尝试；
3）算法实现
2.组合总和
1）题目
组合总和算是一道比较经典的回溯算法题，其中有一道题是这样的：
找出所有相加之和为 n 的 k 个数的组合，组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。
这题说的很明白，就是从1-9中选出k个数字，他们的和等于n，并且这k个数字不能有重复的。
备注：所有数字都是正整数，解集不能包含重复的组合。
2）思路
1）第一次选择的时候可以从这9个数字中任选一个，沿着这个分支走下去；
2）第二次选择的时候还可以从这9个数字中任选一个，但因为不能有重复的；
3）所以要排除第一次选择的，第二次选择的时候只能从剩下的8个数字中选一个；
4）这个选择的过程就比较明朗了，我们可以把它看做一棵9叉树，除叶子结点外每个节点都有9个子节点。
也就是主要，如下图所示：
3）算法实现
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);
}
}
3.全排列问题
1）题目
给定一个没有重复数字的序列，返回其所有可能的全排列。
输入：
输入: [1,2,3]
输出：
输出: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
2）思路
这道题我们可以把它当做一棵3叉树，所以每一步都会有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);
}
}
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》