这一篇文章来讲解一下如何做leetcode回溯算法题目，这一段时间我把leetcode上面的回溯算法的题目都刷了个遍，发现了其中一些规律，所以，就想写一篇文章来总结一下，怕以后忘记。
刷完回溯算法的题目，我发现其实可以总结为三大类：子集问题、组合问题、排列问题，那这三大类都是什么意思呢，我分别举一个例子来说明。
子集问题，比如说，数组[1,2,3]，那么对应的子集问题就是，这个数组的子集有：[],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3]，这就是这个数组的子集，这一类问题在leetcode上面很多个，而且有些题目数组中的元素是可以重复的，然后来求子集问题。
组合问题，比如说，数组[1,2,3]，组合出target为3的可能的选择，那么就有：[1,2],[3]，这就是leetcode中的组合问题。
排列问题，排列问题就比较简单了，比如，我们常见的全排列问题，leetcode也有这一类问题。
这篇文章，我们就来讲讲，怎么用回溯的算法去解决这些问题。
1 一步一步讲解回溯算法框架
最开始，我还是想通过一个简单的例子，一步一步的带大家看一下回溯算法的题目应该是怎么一步一步解决的，最终，通过这个题目，我们就可以大致的整理出一个回溯算法的解题框架；先来看下面这个题目，是一个子集的题目，题目难度中等。
这个题目，题目给的框架是这样的。
public List<List<Integer>> subsets(int[] nums) {
}
所以，我们就知道，我们先构建一个List<List<Integer>>类型的返回值。
List<List<Integer>> list = new ArrayList<>();
接下来，我们就开始写回溯方法。
public void backTrace(int start, int[] nums, List<Integer> temp){
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
最开始，可能写成上面这个样子，传入数组nums，start和temp集合用于保存结果，然后，每次遍历数组nums的时候，都加入当前元素，在递归回来的时候再回溯，删除刚刚加入的元素，这不就是回溯的思想吗。
这样把基本的框架写完了，还有一个需要思考的问题就是base case，那么这个题目的base case是什么呢？其实，因为是子集，每一步都是需要加入到结果集合temp的，所以就没有什么限制条件了。
public void backTrace(int start, int[] nums, List<Integer> temp){
//每次都保存结果
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
最后，我们再补充完整一下，就完整的代码出来了。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
ok，我们去运行一下，看看如何。
他说我超出时间限制，说明算法是有问题的，我们再看一下上面我们写的代码，我们发现，其实我们每次遍历数组的时候都是从0开始遍历的，导致很多重复的元素遍历了，也就是我们得start变量并没有用到，最后，我们把遍历的时候不每次从0开始，而是从当前的start开始遍历，选过的元素我们排除，看一下结果。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//从start开始遍历，避免重复
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
发现完美通过，good job！！
另外，我们要注意一个点就是：list.add(new ArrayList<>(temp));不要写成list.add(temp);，否则，输出的结果就是空集，你思考一下应该就知道为什么了。
通过，这个题目，其实，我们就把回溯算法的一个大致的框架可以整理出来了，以后做其他题目，照猫画虎，一顿操作就可以了。
回到backTrace函数，其实就是一个选择/撤销选择的过程，其中的for循环也是一个选择的过程，还有一个点就是base case需要在这个函数来处理。那么，我们就可以把框架整理出来。
public void backTrace(int start, int[] nums, List<Integer> temp){
base case处理
//选择过程
for(循环选择){
选择
backTrace(递归);
撤销选择
}
}
ok，上面已经讲了一个子集的问题，接下来，再来一个更有点意思的子集的题目。
2 子集问题
用于引入回溯算法框架的那个题目其实比较简单，但是，思想是不变的，这个框架很重要，其他的题目基本上都是在上面的框架上进行修改的，比如，剪枝操作等。
90. 子集 II 中等难度
这个题目与前面的子集题目相比较，差别就在于补鞥呢包含重复的子集，也就是不能顺序改变而已，元素一样的子集出现。
这个题目框架还是不变的，但是，要做一下简单的剪枝操作：怎么排除掉重复的子集。
这里有两种方法可以解决这个问题，而且，后面其他的题目出现不能出现重复子集这样的限制条件的时候，都是可以用这两种方法进行解决的。
- 方法一：利用Set去重特性解题
我们还是先把上面的框架搬下来，然后再进行修改。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//从start开始遍历，避免重复
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
因为我们要利用Set的特性去重，所以需要加入这个变量Set<List<Integer>> set = new HashSet<>();，另外，为了保证顺序，我们再进行排序Arrays.sort(nums)，这样能避免元素一样，但是顺序不一样的重复子集问题。
所以，结果就出来了。
List<List<Integer>> list = new ArrayList<>();
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
//排序
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
//set去重操作
if(!set.contains(temp)){
set.add(new ArrayList<>(temp));
list.add(new ArrayList<>(temp));
}
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
看一下结果发现效率不是很好。
那我们再来看一下另外一种剪枝的策略用来去重。
- 方法二：
i > start && nums[i-1] == nums[i]
这种剪枝策略为什么是可以的呢，别急，我来画张图解释一下。
所以，我们这种方法就可以做出来了。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int i = start; i < nums.length; i++){
//剪枝策略
if(i > start && nums[i] == nums[i-1]){
continue;
}
temp.add(nums[i]);
backTrace(i+1,nums,temp);
temp.remove(temp.size()-1);
}
}
哎呦，好像还可以哦。
3 组合问题
把前面的子集问题搞定之后，你会发现，后面的组合问题，排列问题就都不是什么大问题了，基本上都是套路了。
39. 组合总和 难度中等
这个题目跟之前的没有什么太大的区别，只是需要注意一个点：每个数字可以被无限制重复被选取，我们要做的就是在递归的时候，i的下标不是从i+1开始，而是从i开始。
backTrace(i,candidates,target-candidates[i], temp);
我们看看完整代码。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return list;
}
List<Integer> temp = new ArrayList<>();
backTrace(0,candidates,target,temp);
return list;
}
public void backTrace(int start, int[] candidates, int target, List<Integer> temp){
//递归的终止条件
if (target < 0) {
return;
}
if(target == 0){
list.add(new ArrayList<>(temp));
}
for(int i = start; i < candidates.length; i++){
temp.add(candidates[i]);
backTrace(i,candidates,target-candidates[i], temp);
temp.remove(temp.size()-1);
}
}
就是这么简单！！！
那么，再来一个组合问题。
40. 组合总和 II 难度中等
你一看题目是不是就发现，差不多啊，确实，这里只是每个数字只能用一次，同时也是不能包含重复的组合，所以，用上面的去重方法解决咯。话不多说，上代码。
List<List<Integer>> lists = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return lists;
}
Arrays.sort(candidates);
List<Integer> list = new LinkedList<>();
backTrace(candidates,target,list, 0);
return lists;
}
public void backTrace(int[] candidates, int target, List<Integer> list, int start){
if(target == 0){
lists.add(new ArrayList(list));
}
for(int i = start; i < candidates.length; i++){
if(target < 0){
break;
}
//剪枝：保证同一层中只有1个相同的元素，不同层可以有重复元素
if(i > start && candidates[i] == candidates[i-1]){
continue;
}
list.add(candidates[i]);
backTrace(candidates,target-candidates[i],list,i+1);
list.remove(list.size()-1);
}
}
也是完美解决！！
4 全排列问题
先来一个最基本的全排列问题，快速解决。
46. 全排列 难度中等
这是全排列，只是元素的顺序不一样，所以，我们要做的剪枝就是：temp集合中有的就排除。
上代码。
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0){
return lists;
}
List<Integer> list = new ArrayList<>();
backTrace(nums,list,0);
return lists;
}
public void backTrace(int[] nums, List<Integer> temp, int start){
if(temp.size() == nums.length){
lists.add(new ArrayList(temp));
return;
}
for(int i = 0; i < nums.length; i++){
//排除已有元素
if(temp.contains(nums[i])){
continue;
}
temp.add(nums[i]);
backTrace(nums,temp,i+1);
temp.remove(temp.size() - 1);
}
}
是不是不带劲，安排！！
47. 全排列 II 难度中等
这个题目虽然也是全排列，但是，就要比前面这个难一些了，有两个限定条件：有重复元素，但是不能包含重复排列。
不重复的全排列这个我们知道怎么解决，用前面的去重方法即可，但是，怎么保证有相同元素的集合不出现重复的排列呢？
这里我们需要加一个visited数组，来记录一下当前元素有没有被访问过，这样就可以解题了。
public List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums.length == 0){
return result;
}
Arrays.sort(nums);
findUnique(nums,new boolean[nums.length],new LinkedList<Integer>());
return result;
}
public void findUnique(int[] nums, boolean[] visited,List<Integer> temp){
//结束条件
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return ;
}
//选择列表
for(int i = 0; i<nums.length; i++){
//已经选择过的不需要再放进去了
if(visited[i]) continue;
//去重
if(i>0 && nums[i] == nums[i-1] && visited[i-1]) break;
temp.add(nums[i]);
visited[i] = true;
findUnique(nums,visited,temp);
temp.remove(temp.size()-1);
visited[i] = false;
}
}
这样就搞定了这个题目。
5 不是总结
至此，就把子集、组合、全排列问题给解决了。从一步一步讲解框架，到具体问题分析，面面俱到，哈哈，当然，还有一些没有考虑周到的地方，望大家指教。
这篇文章写了两天了，到这里差不多了，原创不易，点个赞吧！
相关推荐
回溯算法是一种用于求解此类组合优化问题的有效方法。 回溯算法是一种试探性的解决问题的方法，它通过递归地尝试所有可能的解决方案来寻找最优解。当一个分支无法导致有效解时，算法会撤销最近的选择并尝试其他路径...
回溯算法是一种基于深度优先搜索的策略，常用于解决组合优化问题和约束满足问题。它通过尝试构造解的空间树，并逐步扩展当前的解决方案分支，如果在某一节点发现当前选择无法导出有效解，则会撤销这一选择，回溯到上...
北大老师写的kmp无回溯算法，数据结构与算法，大家懂得
回溯算法是一种强大的问题求解方法，尤其在解决复杂组合优化问题时表现出高效性。它是一种试探性的解决问题的方法，通过逐步构建可能的解决方案，并在过程中不断检查这些解决方案的有效性。如果发现当前路径无法导出...
回溯算法是一种强大的问题求解方法，主要用于解决各种组合优化问题和搜索问题。它通过尝试所有可能的解决方案，并在过程中适时地剪枝（剔除不可能的路径）来避免无效的计算，以找到满足条件的最优或可行解。下面将...
回溯算法是一种试探性的解决问题的方法，它在搜索解空间树的过程中，通过不断地尝试来寻找问题的解。在ACM（国际大学生程序设计竞赛）中，回溯算法常常被用来解决那些具有大量可能解且需要尝试多种路径的问题。下面...
通常，这样的作业文件会包含完整的代码、注释和可能的测试用例，帮助学生理解如何实现和调试回溯算法。 总结来说，野人传教士问题的回溯算法解决方案是通过试探性的构建和撤销过河步骤，寻找一个不会使传教士处于...
通过这样的过程，回溯算法可以有效地解决数独问题，而且由于其试探性的特点，即使面对复杂的问题，也能保证找到正确的解，而不会陷入死循环。这种方法不仅适用于数独，还可以应用于其他类似的问题，如八皇后问题、图...
### 使用回溯算法解决0/1背包问题 在计算机科学领域，背包问题是一类经典的组合优化问题，其中0/1背包问题是指给定一组物品，每个物品都有一个重量和一个价值，目标是在不超过背包总承重的情况下，尽可能使得所选...
回溯算法是一种在解决问题时，通过尝试所有可能的解决方案，并在发现不符合条件的解时，及时退回并尝试其他可能性的搜索算法。它常用于解决一些组合优化问题，如八皇后问题、迷宫寻路等。Java作为一种通用的编程语言...
回溯算法是一种在解决问题时，通过尝试所有可能的解决方案，并在每一步中排除那些不可能产生正确结果的选项来寻找问题答案的方法。它主要用于解决约束满足问题，如迷宫求解、八皇后问题、数独填充等。在本例题中，...
回溯算法是一种常用的搜索算法，它可以用于解决许多复杂的问题。回溯算法的基本思想是，通过不断地尝试和回溯来找到问题的解。它可以看作蛮力法穷举搜索的改进，能够避免搜索所有可能的解，从而提高搜索效率。 在...
回溯算法是一种试探性的解决问题的方法，它尝试逐步构建解决方案，并在发现某一步无法达到目标时，退回一步，尝试其他可能的路径。这种“走不通就回头”的策略使得回溯算法适用于解决很多组合优化问题，如找零钱问题...
### 遗传算法与回溯算法在0-1背包问题中的应用 #### 一、0-1背包问题概述 0-1背包问题是一个经典的组合优化问题，在计算机科学和运筹学领域有广泛的应用。该问题的核心是：给定一组物品，每种物品都有自己的重量和...
回溯算法是一种强大的问题求解方法，广泛应用于解决复杂的问题，如组合优化、搜索和图论等。在计算机科学中，回溯算法通常用于在尝试解决问题时，通过系统地探索可能的解决方案空间来找到有效解。它的工作原理是通过...
回溯算法是一种试探性的解决问题的方法，它尝试逐步构建解决方案，并在发现某一步无法达到期望结果时，采取撤销或“回溯”先前的选择，去尝试其他可能的路径。这种算法广泛应用于解决约束满足问题，如图着色、旅行商...
### 回溯算法的核心概念与应用 #### 一、回溯算法的基本思想 回溯算法是一种用于解决问题的有效方法，尤其适用于解决那些具有多种可能解的问题。它的基本思想是从一条路径开始尝试前进，如果可行就继续深入；如果...
根据给定的MATLAB代码和描述，我们可以深入探讨回溯算法和模拟退火算法在解决旅行商问题（TSP）中的应用。 ### 回溯算法 回溯算法是一种通过尝试解决子问题并撤销不成功的解决方案来寻找问题解答的算法。在TSP中，...
回溯算法是一种在搜索解决问题时，通过尝试所有可能的解并逐步缩小搜索空间来找到最优解的方法。在旅行商问题（Traveling Salesman Problem, TSP）中，它被广泛应用于寻找一条经过所有城市且仅访问一次的最短路径。...
由于提供的文件内容主要是对「代码随想录」回溯算法精讲pdf文件的OCR扫描文字，其中存在识别错误和遗漏，导致内容不够连贯和准确。但是，我们依然可以从描述中提炼出关键知识点。 标题“「代码随想录」回溯算法精讲...