目录
什么是回溯算法：
子集问题：
子集问题II(元素可重复但不可复选):
组合问题：
组合问题II(元素可重复但不可复选):
排列问题：
排列问题II(元素可重复但不可复选):
什么是回溯算法：
「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都使用了递归。
详细地说：可以将回溯算法过程理解成一颗多叉树的遍历过程， 回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯问题的基本框架：
void backtrack(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//注意i=0,i=start的区别 处理节点; backtrack(路径，选择列表); // 递归 注意(i)和(i++)的区别 回溯，撤销处理结果 } }
多叉树的遍历：
与二叉树的遍历类似，但要遍历所有的子节点：
public void traverse(TreeNode root){
if(root == null){
return ;
}
//前序遍历的位置
for(Node child : root.children){
traverse(child);
}
//后序遍历的位置
}
如果将前后续遍历的位置放到for循环里面，与上图的区别在于不遍历根节点（通过后面例题加深理解）
那么有了上面的一定了解后，我们看下例题，具体怎么使用框架
子集问题：
问题描述：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
题目链接：78. 子集 - 力扣（LeetCode）
这是一个典型的回溯问题，首先，我们将它模拟成一颗多叉树（根节点为空）：
解决这个问题的关键在于如何遍历这颗多叉树，并且子集不重复 ，在遍历的过程中，我们要将每一个节点都收录到集合中，最后返回这个集合。之后我们只需要让子集不重复就好了，这里我们可以通过设定一个变量start来记录当前走过的位置，使其不断+1来进行迭代，保证不重复，具体实现如下：
class Solution {
//定义二维数组res用于存储结果
List<List<Integer>> res = new LinkedList<>();
//定义路径数组
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums,0);
return res;
}
void backtrack(int[] nums,int start){
//添加路径数组到结果数组中
res.add(new LinkedList<>(track));
//for循环遍历数组nums，这里相当于遍历这颗多叉树
for(int i = start;i < nums.length;i++){
//做选择，将选择添加到路径数组中
track.add(nums[i]);
//回溯，继续向后遍历
backtrack(nums,i + 1);
//撤销选择，将选择从路径中删除
track.removeLast();
}
}
}子集问题II(元素可重复但不可复选):
题目链接：90. 子集 II - 力扣（LeetCode）
输入输出样例：
这里我们以例一为例：为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。
按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：
这里，我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：
体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集，将他们收集
res.add(new LinkedList<>(track));
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
//选择操作
track.addLast(nums[i]);
//回溯
backtrack(nums, i + 1);
//撤销选择
track.removeLast();
}
}
}组合问题：
题目描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
输入输出：
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
题目链接：77. 组合 - 力扣（LeetCode）
还是以 nums = [1,2,3] 为例，刚才让我们求所有子集，就是把所有节点的值都收集起来；现在我们只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// 主函数
public List<List<Integer>> combine(int n, int k) {
backtrack(1, n, k);
return res;
}
void backtrack(int start, int n, int k) {
// base case
if (k == track.size()) {
// 遍历到了第 k 层，收集当前节点的值
res.add(new LinkedList<>(track));
return;
}
// 回溯算法标准框架
for (int i = start; i <= n; i++) {
// 选择
track.addLast(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i + 1, n, k);
// 撤销选择
track.removeLast();
}
}
}组合问题II(元素可重复但不可复选):
题目描述：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
题目链接：39. 组合总和 - 力扣（LeetCode）
上述子集问题中，我们通过变量start+1来控制树的生成，也就是剪枝，但是这题可以无限制选用一个数字，那么剪枝也就没有必要了，这里我们保持start不变（树会一直生成），只需改变base case（限制条件）就行了，同时定义一个trackSum来维护路径和：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的路径和
int trackSum = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates.length == 0) {
return res;
}
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
// base case，找到目标和，记录结果
if (trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
// base case，超过目标和，停止向下遍历
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 选择 nums[i]
trackSum += nums[i];
track.add(nums[i]);
// 递归遍历下一层回溯树
// 同一元素可重复使用，注意参数
backtrack(nums, i, target);
// 撤销选择 nums[i]
trackSum -= nums[i];
track.removeLast();
}
}
}排列问题：
题目描述：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题目链接：46. 全排列 - 力扣（LeetCode）
刚才讲的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择，这就相当于剪枝的作用。将全排列问题模拟成一颗多叉树：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// track 中的元素会被标记为 true
boolean[] used;
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return res;
}
// 回溯算法核心函数
void backtrack(int[] nums) {
// base case，到达叶子节点
if (track.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 已经存在 track 中的元素，不能重复选择
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.addLast(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.removeLast();
used[i] = false;
}
}
}排列问题II(元素可重复但不可复选):
比如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：
[ [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3], [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3], [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3] ]
标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。
代码详解：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> permuteRepeat(int[] nums) {
backtrack(nums);
return res;
}
// 回溯算法核心函数
void backtrack(int[] nums) {
// base case，到达叶子节点
if (track.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.removeLast();
}
}
}最后总结：
回溯算法本质就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
void backtrack(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//注意i=0,i=start的区别
处理节点;
backtrack(路径，选择列表); // 递归 注意(i)和(i++)的区别
回溯，撤销处理结果
}
}写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。 最后返回结果集合，得到答案。
结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固自己的知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+关注+收藏，你们的鼓励是我创作的最大动力！
