在上一篇文章 算法模式：回溯 介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。本篇文章，介绍一种无需“一步三回头”，无需“落棋有悔”也可以解决排列组合问题的算法模式：子集。
子集 超级多的编程面试问题都会涉及到排列和组合问题。一般都是使用回溯来解决该类问题，回溯法属于 深度优先搜索。子集问题模式讲的是用 广度优先搜索 来处理这些问题。子集模式适用于子集与全排列。下面分别介绍：
处理子集问题 举例来说明一下这个模式：
给一组数字 [1, 5, 3]
我们从空集开始：[[]]
把第一个数 1，加到之前已经存在的集合中：[[], [1]];
把第二个数 5，加到之前的集合中得到：[[], [1], [5], [1,5]];
再加第三个数 3，则有：[[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].
如果原有集合中存在重复元素，那么就需要针对这种情况特殊处理一下。流程如下：
给一组数字 [5, 1, 5]
先对原有集合进行排序： [1, 5, 3]
从空集开始：[[]]
把第一个数 1，加到之前已经存在的集合中：[[], [1]];
把第二个数 5，加到之前的集合中得到：[[], [1], [5], [1,5]];
处理第三个数，也是 5 时需要注意：
如果还是按照上述方案处理，那么就会得到如下结果： [[], [1], [5], [1,5], [5], [1, 5], [5, 5], [1,5, 5]]。这里出现了重复子集： [5], [1, 5]。该方案不通过，❌
观察最后生成的所有子集与重复的子集，会发现重复的子集，在处理第二个数时，已经处理过 [], [1]，如果再次处理 5，那么就会出现重复。所以，只需要处理在处理上一个相同的数时新增加的子集即可。上一个相同数新增的子集是 [5], [1,5]，只需要在这些子集后面增加当前数字即可。这样最后的子集就是：[[], [1], [5], [1,5], [5, 5], [1,5, 5]]。方案通过 ✅
在上一篇文章 算法模式：变治法 介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：变治法。本篇文章，介绍一种“一步三回头”、“落棋有悔”的算法模式：回溯。
回溯 “回溯”算法也叫“回溯搜索”算法，主要用于在一个庞大的空间里搜索我们所需要的问题的解。我们每天使用的“搜索引擎”就是帮助我们在庞大的互联网上搜索我们需要的信息。“搜索”引擎的“搜索”和“回溯搜索”算法的“搜索”意思是一样的。
“回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。
“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 \$N!\$ 这么多个。
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。
说明：
每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现；
这些变量的不同的值，也称之为“状态”；
使用深度优先遍历有“回头”的过程，在“回头”以后，状态变量需要设置成为和先前一样；
因此在回到上一层结点的过程中，需要撤销上一次选择，这个操作也称之为“状态重置”；
深度优先遍历，可以直接借助系统栈空间，为我们保存所需要的状态变量，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈。
深度优先遍历通过“回溯”操作，实现了全局使用一份状态变量的效果。
解决一个回溯问题，实际上就是一个决策树的遍历过程。只需要思考 3 个问题：
路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。
这三个问题也就对应回溯三部曲：
定义递归函数以及参数
确定递归终止条件
思考递归单层搜索逻辑
代码方面，回溯算法的框架：
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 \$O(N!)\$，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
玩回溯，一定要画出递归调用树。这样可以帮助我们更深入地理解整个回溯的过程，方便进一步剪枝优化。
回溯优化，重要的是，要学会剪枝！
LeetCode 46. 全排列 LeetCode - 46. 全排列 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
在上一篇文章 算法模式：分治法 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：变治法。
变治法 D瓜哥最早知道变治法也是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。
变治法，就是基于变换的一种思想方法，首先把问题的实例变得容易求解，然后进行求解。
变治法的工作可以分成两个阶段：首先把问题变得更容易求解，然后对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型：
实例化简(Instance simplification) — 指将原问题变换为同样问题的一个更简单或者更方便的实例。一个典型的案例是：去重时，先排序，
列表预排序
检验数组中元素的唯一性
模式计算
查找问题
高斯消元法
系数矩阵的LU分解(LU decomposition)
计算矩阵的逆
计算矩阵的行列式
AVL 树
改变表现(Representation Change) — 指将原问题变换为同样实例的不同表现。经典的栗子：霍纳法则。
多路平衡查找树（最简单的情况：2-3树）
求多项式的霍纳法则
两种二进制幂算法
堆排序
问题化简(Problem reduction) — 指把一个给定的问题变换为另一个可以用已知算法求解的问题。（归化思想）转换的难题在于如何找到一个变换的目标算法。典型案例是背包问题，背包问题的本质是线性规划。了解了线性规划的本质后，才能更好地解决高维的背包问题。
求最小公倍数
计算图中的路径数量
最优化问题（最大化问题(maximization problem)、最小化问题(minimization problem)）
线性规划（单纯形法、0/1背包问题）
简化为图问题
LeetCode 474. 一和零 LeetCode - 474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
在上一篇文章 算法模式：减治法 介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：减治法。本篇文章，继续介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：分治法。
分治法 关于分治法的内容，这里继续参考 《算法设计与分析基础》 中的内容。
分治法是按照以下方案工作的。
将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。
有必要的话，合并这些子问题的解，以得到原始问题的答案。
图 1. 分治法 从字面上分析就可以看到有哪些步骤：
分-分解-将问题分解为规模更小的子问题，子问题最好相同或相似；
治-求解-将这些规模更小的子问题逐个击破；
合-合并-将已解决的子问题合并，最终得出原问题的解；
从上述步骤中我们可以看出，分治算法一般适用满足以下条件的场景：
问题规模缩小到一定的程度就可以很容易解决；
问题可以分解为若干个规模较小的相同问题；
问题分解出的若干子问题的解可以合并为该问题的解；
每个子问题都是独立的，相互之间没有交集。（这是区别分治法与减）
在“分”的过程中，我们尽可能让分解出的子问题与原始问题相似，而规模更小。这刚好符合递归的特性。因此，分治法往往与递归联系在一起。
在分治法最典型的运用中，问题规模为 n 的实例被划分为两个规模为 n/2 的实例。更一般的情况下，一个规模为 n 的实例可以划分为 b 个规模为 n/b 的实例，其中 a 个实例需要求解（这里，a 和 b 是常量，a≥1，b>1）。
\$T(n) = aT(n/b) + f(n)\$ 其中，\$f(n)\$ 是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间
分治法的典型案例如下：
归并排序
快速排序
二叉树的经典遍历算法和其他类似的算法都需要递归处理左右两棵子树
Strassen 算法
最近对问题
凸包问题
分治法对分治出的部分需要分别处理，进行分开的单独计算，而减治法则利用了"一个问题给定实例的解和同样问题较小实例的解之间的关系"，只针对部分子问题求解，减治掉的那部分就不需要了。
减常因子的减治法也可以看做是分治的变种。
LeetCode 148. 排序链表 LeetCode - 148. 排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
在上一篇文章 算法模式：拓扑排序 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：减治法。
减治法 D瓜哥最早知道减治法是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。
减治(decrease-and-conquer)技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。自底向上版本往往是迭代实现的，从求解问题的一个较小实例开始，该方法有时也称为增量法(Incremental Approach)。
减治法有3种主要的变化形式：
减去一个常量。在减常量(decrease-by-a-constant)变化形式中，每次算法迭代总是从实例中减去一个相同的常量。
插入排序
减去一个常量因子。减常因子(decrease-by-a-constant-factor)技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在大多数应用中，这样的常数因子等于2，其实就是减半。
二分查找
减去的规模是可变的。在减治法的减可变规模(variable-size-decrease)变化形式中，算法在每次迭代时，规模减小的模式都是不同的。
计算最大公约数的欧几里得算法是这种情况的一个很好的例子。 \$gcd(m, n)=gcd(n,m mod n)\$
LeetCode 50. Pow(x, n) LeetCode - 50. Pow(x, n) 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000 示例 2：
输入：x = 2.10000, n = 3 输出：9.26100 示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25 提示：
在上一篇文章 算法模式：并查集 介绍一种关于特殊的树的算法模式：并查集。本篇文章，介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。
拓扑排序 拓扑排序模式用来寻找一种线性的顺序，这些元素之间具有依懒性。比如，如果事件 B 依赖于事件 A，那 A 在拓扑排序顺序中排在 B 的前面。
这种模式定义了一种简单方式来理解拓扑排序这种技术。
这种模式是这样奏效的：
初始化
借助于 Map 将图保存成邻接表形式。
找到所有的起点，用 Map 来帮助记录每个节点的入度
创建图，找到每个节点的入度
利用输入，把图建好，然后遍历一下图，将入度信息记录在 Map 中
找所有的起点
所有入度为 0 的节点，都是有效的起点，而且我们讲他们都加入到一个队列中
排序
对每个起点，执行以下步骤
把它加到结果的顺序中
将其在图中的孩子节点取到
将其孩子的入度减少1
如果孩子的入度变为0，则改孩子节点成为起点，将其加入队列中
重复上述过程，直到起点队列为空。
用一句话概括：将依赖关系转化成一张有向图，如果这张图中的节点没有循环依赖，那么则方案可行，否则方案不可行。
这里解释的是一种广度优先搜索，还存在一种深度优先搜索的处理办法，感兴趣可以尝试一下。 拓扑排序模式识别：
待解决的问题需要处理无环图
你需要以一种有序的秩序更新输入元素
需要处理的输入遵循某种特定的顺序
LeetCode 207. 课程表 LeetCode - 207. 课程表 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则 必须 先学习课程 bi。
在上一篇文章 算法模式：前缀树 介绍一种关于特殊的树的算法模式。本篇文章，再介绍一种关于特殊的树的算法模式：并查集。
并查集 并查集算法，英文是 Union-Find，是解决动态连通性（Dynamic Conectivity）问题的一种算法。动态连通性是计算机图论中的一种数据结构，动态维护图结构中相连信息。简单的说就是，图中各个节点之间是否相连、如何将两个节点连接，连接后还剩多少个连通分量。
动态连通性其实可以抽象成给一幅图连线。假设用一个数组表示一堆节点，每个节点都是一个连通分量。初始化视图如下：
图 1. 并查集初始化 并查集的一个重要操作是 union(a, b)，就是将节点 a 和节点 b 建立连接。如图所示：
图 2. 并查集合并 union(a, b) 还可以将已经建立的两个“子网”进行连接：
图 3. 并查集再合并 并查集除了 union，还有一个重要操作是 connnected(a, b)。判断方法也很简单，从节点 a 和 b 开始，向上查找，直到两个节点的根节点，判断两个根节点是否相等即可判断两个节点是否已经连接。为了加快这个判断速度，可以对其进行“路径压缩”，直白点说，就是将所有树的节点，都直接指向根节点，这样只需要一步即可到达根节点。路径压缩如图所示：
图 4. 并查集路径压缩 简单代码实现如下：
package com.diguage.labs; import java.util.ArrayList; import java.util.List; /** * 并查集 * * PS：没想到代码竟然一次通过。 * * @author D瓜哥 · https://www.diguage.com * @since 2025-04-03 15:22:41 */ public class UnionFind { /** * 连通分量 */ private int size; /** * 每个节点及对应的父节点 */ private int[] parent; public UnionFind(int size) { this.size = size; parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } } /** * a 和 b 建立连接 */ public void union(int a, int b) { int ap = find(a); int bp = find(b); if (ap == bp) { return; } parent[ap] = bp; size--; } /** * a 和 b 是否连通 */ public boolean connected(int a, int b) { int ap = find(a); int bp = find(b); return ap == bp; } /** * 连通分量 */ public int count() { return size; } /** * 查找节点 a 的根节点 */ private int find(int a) { int ap = parent[a]; if (a != ap) { List<Integer> path = new ArrayList<>(); path.add(a); // 向上查找根节点 while (parent[ap] != ap) { path.add(ap); ap = parent[ap]; } // 路径压缩 // 只有一步，无需缩短路径 if (path.size() == 1) { return ap; } for (Integer idx : path) { parent[idx] = ap; } } return ap; } public static void main(String[] args) { UnionFind uf = new UnionFind(10); uf.union(0, 1); uf.union(1, 2); uf.union(2, 3); uf.union(3, 4); uf.union(5, 6); uf.union(6, 7); uf.union(7, 8); uf.union(8, 9); uf.union(0, 5); System.out.println(uf.count() + ", " + uf.connected(0, 9)); System.out.println(uf.count() + ", " + uf.connected(2, 9)); System.out.println(uf.count() + ", " + uf.connected(3, 9)); System.out.println(uf.count() + ", " + uf.connected(5, 9)); } }
在上一篇文章 算法模式：深度优先搜索 介绍了介绍一种即适用于树，又适用于图的的算法模式。本篇文章，介绍一种关于特殊的树的算法模式：前缀树。
前缀树 前缀树，又称为字典树，还叫单词查找树，英文是 Trie，也有叫 Prefix Tree。顾名思义，就是一个像字典一样的树。如图：
图 1. 前缀树 前缀树是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
LeetCode 208. 实现 Trie (前缀树) LeetCode - 208. 实现 Trie (前缀树) Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true] 解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True
在上一篇文章 算法模式：广度优先搜索 介绍了介绍一种即适用于树，又适用于图的的算法模式。本篇文章，继续介绍一种即适用于树，又适用于图的的算法模式：深度优先搜索。
深度优先搜索 深度优先搜索主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
树是图的一种特例(连通无环的图就是树)，所以，深度优先搜索也适用于树。
在对树做深度优先搜索时，可以用递归（或显式栈，如果你想用迭代方式的话）来记录遍历过程中访问过的父节点。运行方式是从根节点开始，如果该节点不是叶子节点，我们需要干三件事：
需要区别我们是先处理根节点（pre-order，前序），处理孩子节点之间处理根节点（in-order，中序），还是处理完所有孩子再处理根节点（post-order，后序）。
递归处理当前节点的左右孩子。
LeetCode 124. 二叉树中的最大路径和 LeetCode - 124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
1 / \ 2 3 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例 2：
-10 / \ 9 20 / \ 15 7 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
在上一篇文章 算法模式：多路归并 介绍了一种利用堆做链表合并的算法模式。本篇文章，介绍一种即适用于树，又适用于图的的算法模式：广度优先搜索。
广度优先搜索 广度优先搜索既适用于树，又适用于图。除此之外，在处理一些矩阵问题时，也会用到广度优先搜索的思想。当然，也可以把矩阵按照图来理解。
树上的广度优先搜索模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。
识别树上的广度优先搜索：
如果你被问到去遍历树，需要按层操作的方式（也称作层序遍历）
LeetCode 102. 二叉树的层序遍历 LeetCode - 102. 二叉树的层序遍历 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] 示例 2：
输入：root = [1] 输出：[[1]] 示例 3：
输入：root = [] 输出：[] 提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
思路分析 思路与上述描述类似，这里直接看图：
图 1. 广度优先搜索 代码如下：
/** * @author D瓜哥 · https://www.diguage.com * @since 2025-03-31 07:31:39 */ public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return Collections.emptyList(); } List<List<Integer>> result = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); // 将下一层节点，从左到右，依次加入到队列中 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }