个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰经过一段时间的学习我们终于走完了二叉树的初步章节但这些题目肯定是不够的相当于是大致的过了一边我们继续学习数据结构与算法这一章节要学的是回溯算法回溯算法前置了解什么是回溯算法回溯算法本质上是一种暴力穷举的搜索方法通过尝试所有可能的路径来解决问题。它在尝试过程中当发现当前路径不可行时就回退到上一步或之前某步换一条路继续尝试。核心思想前进做出选择进入下一层回退撤销选择回到之前的状态剪枝提前判断当前路径不可能成功直接跳过可以用一个经典比喻理解走迷宫时每遇到岔路口就选择一个方向如果走不通就原路返回换个方向继续走。回溯算法能解决什么问题问题类型经典例子组合问题从 n 个数中选 k 个数的所有组合排列问题全排列、有重复元素的全排列子集问题求所有子集、有重复元素的子集分割问题分割回文串、复原 IP 地址棋盘问题N 皇后、数独、解数独路径问题矩阵中的路径、单词搜索回溯法的效率回溯法的性能如何呢这里要和大家说清楚了虽然回溯法很难很不好理解但是回溯法并不是什么高效的算法。因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。那么既然回溯法并不高效为什么还要用它呢因为没得选一些问题能暴力搜出来就不错了撑死了再剪枝一下还没有更高效的解法。如何理解回溯法回溯法解决的问题都可以抽象为树形结构是的指的是所有回溯法的问题都可以抽象为树形结构因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。递归就要有终止条件所以必然是一棵高度有限的树N叉树。这块可能初学者还不太理解后面的回溯算法解决的所有题目中我都会强调这一点并画图举相应的例子现在有一个印象就行回溯算法的模板回溯函数模板返回值以及参数在回溯算法中我的习惯是函数起名字为backtracking这个起名大家随意。回溯算法中函数返回值一般为void。再来看一下参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。但后面的回溯题目的讲解中为了方便大家理解我在一开始就帮大家把参数确定下来。回溯函数伪代码如下void backtracking(参数)回溯函数终止条件既然是树形结构那么我们在讲解二叉树的递归 (opens new window)的时候就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。所以回溯函数终止条件伪代码如下if (终止条件) { 存放结果; return; }回溯搜索的遍历过程在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。如图回溯函数遍历过程伪代码如下for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 }for循环就是遍历集合区间可以理解一个节点有多少个孩子这个for循环就执行多少次。backtracking这里自己调用自己实现递归。大家可以从图中看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了。分析完过程回溯算法模板框架如下void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 } }这份模板很重要后面做回溯法的题目都靠它了如果从来没有学过回溯算法的录友们看到这里会有点懵后面开始讲解具体题目的时候就会好一些了已经做过回溯法题目的录友看到这里应该会感同身受了类比理解想象一个场景你在食堂打菜假设食堂今天有 3 道菜菜A红烧肉菜B炒青菜菜C番茄蛋你要打2 道菜顺序不重要组合问题。什么是树的深度 / 递归层数深度 你已经选了几道菜第 0 层还没开始选空盘子第 1 层选了第 1 道菜第 2 层选了第 2 道菜达到目标停止深度 你总共要选几次k上图中 size:3 → 2 → 1 → 0其实就是在说每选一道菜剩下的选择就少一个什么是每层有多少个节点节点 在这一步时你的盘子状态具体展开第 0 层空盘子节点数 1只有一种状态啥都没选第 1 层选第 1 道菜可选A、B、C选 A → 状态 [A]选 B → 状态 [B]选 C → 状态 [C]节点数 3第 2 层选第 2 道菜从 [A] 出发可选 B、C → [A,B]、[A,C]从 [B] 出发可选 C → [B,C]从 [C] 出发没有可选 → 无节点数 3总结这个例子层数深度含义这一层有多少个节点不同状态0还没选11选了第 1 道菜32选了第 2 道菜3有效解题目背景77.组合给定两个整数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]]提示1 n 201 k n题目解析本题是回溯法的经典题目。直接的解法当然是使用for循环例如示例中k为2很容易想到 用两个for循环这样就可以输出 和示例中一样的结果。如果n为100k为50呢那就50层for循环是不是开始窒息。此时就会发现虽然想暴力搜索但是用for循环嵌套连暴力都写不出来因此回溯搜索法来了虽然回溯法也是暴力但至少能写出来不像for循环嵌套k层让人绝望。那么回溯法怎么暴力搜呢上面我们说了要解决 n为100k为50的情况暴力写法需要嵌套50层for循环那么回溯法就用递归来解决嵌套层数的问题。递归来做层叠嵌套可以理解是开k层for循环每一次的递归中嵌套一个for循环那么递归就可以用于解决多层嵌套循环的问题了。此时递归的层数大家应该知道了例如n为100k为50的情况下就是递归50层。具体示例如图可以看出这棵树一开始集合是 1234 从左向右取数取过的数不再重复取。第一次取1集合变为234 因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3] [1,4]以此类推。每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围。图中可以发现n相当于树的宽度k相当于树的深度。那么如何在这个树上遍历然后收集到我们要的结果集呢图中每次搜索到了叶子节点我们就找到了一个结果。相当于只需要把达到叶子节点的结果收集起来就可以求得 n个数中k个数的组合集合。具体步骤递归函数的返回值以及参数在这里要定义两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。其实不定义这两个全局变量也是可以的把这两个变量放进递归函数的参数里但函数里参数太多影响可读性所以我定义全局变量了。函数里一定有两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。为什么要有这个startIndex呢从下图中红线部分可以看出在集合[1,2,3,4]取1之后下一层递归就要在[2,3,4]中取数了那么下一层递归如何知道从[2,3,4]中取数呢靠的就是startIndex。所以需要startIndex来记录下一层递归搜索的起始位置。回溯函数终止条件什么时候到达所谓的叶子节点了呢path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。如图红色部分此时用result二维数组把path保存起来并终止本层递归。单层搜索的过程回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。如此我们才遍历完图中的这棵树。for循环每次从startIndex开始遍历然后用path保存取到的节点i。具体回溯实例第1步进入backtrack(4, 2, 1)textpath.size()0, 不等于2, 进入for循环 start1, 循环 i1,2,3,4i1 的分支① 做选择: path.add(1) → path[1] ② 递归: backtrack(4, 2, i12) ├─ 进入 backtrack(4, 2, 2) │ path.size()1, 不等于2, for循环 i2,3,4 │ │ **i2:** │ ① path.add(2) → path[1,2] │ ② 递归: backtrack(4, 2, 3) │ └─ path.size()2 k → 记录结果: result.add([1,2]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ │ **i3:** │ ① path.add(3) → path[1,3] │ ② 递归: backtrack(4, 2, 4) │ └─ path.size()2 k → 记录结果: result.add([1,3]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ │ **i4:** │ ① path.add(4) → path[1,4] │ ② 递归: backtrack(4, 2, 5) │ └─ path.size()2 k → 记录结果: result.add([1,4]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ └─ 返回到上一层 ③ 撤销选择: path.remove() → path[]此时 result [[1,2], [1,3], [1,4]]大体的流程就是这样题目答案class Solution { // 存放最终结果 ListListInteger result new ArrayList(); // 存放当前路径一次正在构建的组合 ListInteger path new ArrayList(); public ListListInteger combine(int n, int k) { backtrack(n, k, 1); return result; } /** * 回溯函数 * param n 数字范围 1~n * param k 目标组合大小 * param start 当前层可以从哪个数开始选避免重复 */ private void backtrack(int n, int k, int start) { // 终止条件path中已经有k个数了 if (path.size() k) { result.add(new ArrayList(path)); // 注意要new一个副本 return; } // 横向遍历从start到n for (int i start; i n; i) { // ① 做选择把i加入路径 path.add(i); // ② 递归进入下一层下一层从 i1 开始组合不讲究顺序 backtrack(n, k, i 1); // ③ 撤销选择回溯把i从路径中移除 path.remove(path.size() - 1); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】一篇搞懂回溯算法模板，附77.组合详解
个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰经过一段时间的学习我们终于走完了二叉树的初步章节但这些题目肯定是不够的相当于是大致的过了一边我们继续学习数据结构与算法这一章节要学的是回溯算法回溯算法前置了解什么是回溯算法回溯算法本质上是一种暴力穷举的搜索方法通过尝试所有可能的路径来解决问题。它在尝试过程中当发现当前路径不可行时就回退到上一步或之前某步换一条路继续尝试。核心思想前进做出选择进入下一层回退撤销选择回到之前的状态剪枝提前判断当前路径不可能成功直接跳过可以用一个经典比喻理解走迷宫时每遇到岔路口就选择一个方向如果走不通就原路返回换个方向继续走。回溯算法能解决什么问题问题类型经典例子组合问题从 n 个数中选 k 个数的所有组合排列问题全排列、有重复元素的全排列子集问题求所有子集、有重复元素的子集分割问题分割回文串、复原 IP 地址棋盘问题N 皇后、数独、解数独路径问题矩阵中的路径、单词搜索回溯法的效率回溯法的性能如何呢这里要和大家说清楚了虽然回溯法很难很不好理解但是回溯法并不是什么高效的算法。因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案如果想让回溯法高效一些可以加一些剪枝的操作但也改不了回溯法就是穷举的本质。那么既然回溯法并不高效为什么还要用它呢因为没得选一些问题能暴力搜出来就不错了撑死了再剪枝一下还没有更高效的解法。如何理解回溯法回溯法解决的问题都可以抽象为树形结构是的指的是所有回溯法的问题都可以抽象为树形结构因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。递归就要有终止条件所以必然是一棵高度有限的树N叉树。这块可能初学者还不太理解后面的回溯算法解决的所有题目中我都会强调这一点并画图举相应的例子现在有一个印象就行回溯算法的模板回溯函数模板返回值以及参数在回溯算法中我的习惯是函数起名字为backtracking这个起名大家随意。回溯算法中函数返回值一般为void。再来看一下参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。但后面的回溯题目的讲解中为了方便大家理解我在一开始就帮大家把参数确定下来。回溯函数伪代码如下void backtracking(参数)回溯函数终止条件既然是树形结构那么我们在讲解二叉树的递归 (opens new window)的时候就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。所以回溯函数终止条件伪代码如下if (终止条件) { 存放结果; return; }回溯搜索的遍历过程在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。如图回溯函数遍历过程伪代码如下for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 }for循环就是遍历集合区间可以理解一个节点有多少个孩子这个for循环就执行多少次。backtracking这里自己调用自己实现递归。大家可以从图中看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了。分析完过程回溯算法模板框架如下void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归 回溯撤销处理结果 } }这份模板很重要后面做回溯法的题目都靠它了如果从来没有学过回溯算法的录友们看到这里会有点懵后面开始讲解具体题目的时候就会好一些了已经做过回溯法题目的录友看到这里应该会感同身受了类比理解想象一个场景你在食堂打菜假设食堂今天有 3 道菜菜A红烧肉菜B炒青菜菜C番茄蛋你要打2 道菜顺序不重要组合问题。什么是树的深度 / 递归层数深度 你已经选了几道菜第 0 层还没开始选空盘子第 1 层选了第 1 道菜第 2 层选了第 2 道菜达到目标停止深度 你总共要选几次k上图中 size:3 → 2 → 1 → 0其实就是在说每选一道菜剩下的选择就少一个什么是每层有多少个节点节点 在这一步时你的盘子状态具体展开第 0 层空盘子节点数 1只有一种状态啥都没选第 1 层选第 1 道菜可选A、B、C选 A → 状态 [A]选 B → 状态 [B]选 C → 状态 [C]节点数 3第 2 层选第 2 道菜从 [A] 出发可选 B、C → [A,B]、[A,C]从 [B] 出发可选 C → [B,C]从 [C] 出发没有可选 → 无节点数 3总结这个例子层数深度含义这一层有多少个节点不同状态0还没选11选了第 1 道菜32选了第 2 道菜3有效解题目背景77.组合给定两个整数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]]提示1 n 201 k n题目解析本题是回溯法的经典题目。直接的解法当然是使用for循环例如示例中k为2很容易想到 用两个for循环这样就可以输出 和示例中一样的结果。如果n为100k为50呢那就50层for循环是不是开始窒息。此时就会发现虽然想暴力搜索但是用for循环嵌套连暴力都写不出来因此回溯搜索法来了虽然回溯法也是暴力但至少能写出来不像for循环嵌套k层让人绝望。那么回溯法怎么暴力搜呢上面我们说了要解决 n为100k为50的情况暴力写法需要嵌套50层for循环那么回溯法就用递归来解决嵌套层数的问题。递归来做层叠嵌套可以理解是开k层for循环每一次的递归中嵌套一个for循环那么递归就可以用于解决多层嵌套循环的问题了。此时递归的层数大家应该知道了例如n为100k为50的情况下就是递归50层。具体示例如图可以看出这棵树一开始集合是 1234 从左向右取数取过的数不再重复取。第一次取1集合变为234 因为k为2我们只需要再取一个数就可以了分别取234得到集合[1,2] [1,3] [1,4]以此类推。每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围。图中可以发现n相当于树的宽度k相当于树的深度。那么如何在这个树上遍历然后收集到我们要的结果集呢图中每次搜索到了叶子节点我们就找到了一个结果。相当于只需要把达到叶子节点的结果收集起来就可以求得 n个数中k个数的组合集合。具体步骤递归函数的返回值以及参数在这里要定义两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合。其实不定义这两个全局变量也是可以的把这两个变量放进递归函数的参数里但函数里参数太多影响可读性所以我定义全局变量了。函数里一定有两个参数既然是集合n里面取k个数那么n和k是两个int型的参数。然后还需要一个参数为int型变量startIndex这个参数用来记录本层递归的中集合从哪里开始遍历集合就是[1,...,n] 。为什么要有这个startIndex呢从下图中红线部分可以看出在集合[1,2,3,4]取1之后下一层递归就要在[2,3,4]中取数了那么下一层递归如何知道从[2,3,4]中取数呢靠的就是startIndex。所以需要startIndex来记录下一层递归搜索的起始位置。回溯函数终止条件什么时候到达所谓的叶子节点了呢path这个数组的大小如果达到k说明我们找到了一个子集大小为k的组合了在图中path存的就是根节点到叶子节点的路径。如图红色部分此时用result二维数组把path保存起来并终止本层递归。单层搜索的过程回溯法的搜索过程就是一个树型结构的遍历过程在如下图中可以看出for循环用来横向遍历递归的过程是纵向遍历。如此我们才遍历完图中的这棵树。for循环每次从startIndex开始遍历然后用path保存取到的节点i。具体回溯实例第1步进入backtrack(4, 2, 1)textpath.size()0, 不等于2, 进入for循环 start1, 循环 i1,2,3,4i1 的分支① 做选择: path.add(1) → path[1] ② 递归: backtrack(4, 2, i12) ├─ 进入 backtrack(4, 2, 2) │ path.size()1, 不等于2, for循环 i2,3,4 │ │ **i2:** │ ① path.add(2) → path[1,2] │ ② 递归: backtrack(4, 2, 3) │ └─ path.size()2 k → 记录结果: result.add([1,2]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ │ **i3:** │ ① path.add(3) → path[1,3] │ ② 递归: backtrack(4, 2, 4) │ └─ path.size()2 k → 记录结果: result.add([1,3]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ │ **i4:** │ ① path.add(4) → path[1,4] │ ② 递归: backtrack(4, 2, 5) │ └─ path.size()2 k → 记录结果: result.add([1,4]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path[1] │ └─ 返回到上一层 ③ 撤销选择: path.remove() → path[]此时 result [[1,2], [1,3], [1,4]]大体的流程就是这样题目答案class Solution { // 存放最终结果 ListListInteger result new ArrayList(); // 存放当前路径一次正在构建的组合 ListInteger path new ArrayList(); public ListListInteger combine(int n, int k) { backtrack(n, k, 1); return result; } /** * 回溯函数 * param n 数字范围 1~n * param k 目标组合大小 * param start 当前层可以从哪个数开始选避免重复 */ private void backtrack(int n, int k, int start) { // 终止条件path中已经有k个数了 if (path.size() k) { result.add(new ArrayList(path)); // 注意要new一个副本 return; } // 横向遍历从start到n for (int i start; i n; i) { // ① 做选择把i加入路径 path.add(i); // ② 递归进入下一层下一层从 i1 开始组合不讲究顺序 backtrack(n, k, i 1); // ③ 撤销选择回溯把i从路径中移除 path.remove(path.size() - 1); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
