【LeetCode刷题日记】一篇搞懂回溯算法模板，附77.组合详解

🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好我是代码不加冰，经过一段时间的学习，我们终于走完了二叉树的初步章节，但这些题目肯定是不够的，相当于是大致的过了一边，我们继续学习数据结构与算法，这一章节要学的是回溯算法！

回溯算法前置了解：

什么是回溯算法

回溯算法本质上是一种暴力穷举的搜索方法，通过尝试所有可能的路径来解决问题。它在尝试过程中，当发现当前路径不可行时，就回退到上一步（或之前某步），换一条路继续尝试。

核心思想：

• 前进：做出选择，进入下一层

• 回退：撤销选择，回到之前的状态

• 剪枝：提前判断当前路径不可能成功，直接跳过

可以用一个经典比喻理解：

走迷宫时，每遇到岔路口就选择一个方向，如果走不通，就原路返回，换个方向继续走。

回溯算法能解决什么问题

回溯法的效率

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，是的，指的是所有回溯法的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（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	还没选	1
1	选了第 1 道菜	3
2	选了第 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 <= 20
• 1 <= k <= n

题目解析：

本题是回溯法的经典题目。

直接的解法当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。

如果n为100，k为50呢，那就50层for循环，是不是开始窒息。

此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来

因此：

回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。

那么回溯法怎么暴力搜呢

上面我们说了要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。

递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。

具体示例如图：

可以看出这棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不再重复取。

第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[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)

text

path.size()=0, 不等于2, 进入for循环 start=1, 循环 i=1,2,3,4

i=1 的分支

① 做选择: path.add(1) → path=[1] ② 递归: backtrack(4, 2, i+1=2) ├─ 进入 backtrack(4, 2, 2) │ path.size()=1, 不等于2, for循环 i=2,3,4 │ │ **i=2:** │ ① path.add(2) → path=[1,2] │ ② 递归: backtrack(4, 2, 3) │ └─ path.size()=2 == k → 记录结果: result.add([1,2]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path=[1] │ │ **i=3:** │ ① path.add(3) → path=[1,3] │ ② 递归: backtrack(4, 2, 4) │ └─ path.size()=2 == k → 记录结果: result.add([1,3]) │ └─ 返回 │ ③ 撤销选择: path.remove() → path=[1] │ │ **i=4:** │ ① 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 { // 存放最终结果 List<List<Integer>> result = new ArrayList<>(); // 存放当前路径（一次正在构建的组合） List<Integer> path = new ArrayList<>(); public List<List<Integer>> 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); // ② 递归：进入下一层，下一层从 i+1 开始（组合不讲究顺序） backtrack(n, k, i + 1); // ③ 撤销选择：回溯，把i从路径中移除 path.remove(path.size() - 1); } } }

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！