枚举算法（Enumeration Algorithm）：也称为穷举算法，指的是按照问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中，既不能遗漏也不能重复。

枚举算法的核心思想是：通过列举问题的所有状态，将它们逐一与目标状态进行比较，从而得到满足条件的解。

由于枚举算法要通过列举问题的所有状态来得到满足条件的解，因此，在问题规模变大时，其效率一般是比较低的。但是枚举算法也有自己特有的优点：

多数情况下容易编程实现，也容易调试。

建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。

所以，枚举算法通常用于求解问题规模比较小的问题，或者作为求解问题的一个子算法出现，通过枚举一些信息并进行保存，而这些消息的有无对主算法效率的高低有着较大影响。

枚举算法是设计最简单、最基本的搜索算法。是我们在遇到问题时，最应该优先考虑的算法。

因为其实现足够简单，所以在遇到问题时，我们往往可以先通过枚举算法尝试解决问题，然后在此基础上，再去考虑其他优化方法和解题思路。

采用枚举算法解题的一般思路如下：

确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。

一一枚举可能的情况，并验证是否是问题的解。

考虑提高枚举算法的效率。

我们可以从下面几个方面考虑提高算法的效率：

抓住问题状态的本质，尽可能缩小问题状态空间的大小。

加强约束条件，缩小枚举范围。

根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。

下面举个著名的例子：「百钱买百鸡问题」。这个问题是我国古代数学家张丘在「算经」一书中提出的。该问题叙述如下：

百钱买百鸡问题：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则鸡翁、鸡母、鸡雏各几何？

翻译一下，意思就是：公鸡一只五块钱，母鸡一只三块钱，小鸡三只一块钱。现在我们用 $100$ 块钱买了 $100$ 只鸡，问公鸡、母鸡、小鸡各买了多少只？

下面我们根据算法的一般思路来解决一下这道题。

确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。

确定枚举对象：枚举对象为公鸡、母鸡、小鸡的只数，那么我们可以用变量 $x$、$y$、$z$ 分别来代表公鸡、母鸡、小鸡的只数。

确定枚举范围：因为总共买了 $100$ 只鸡，所以 $0 \le x, y, z \le 100$，则 $x$、$y$、$z$ 的枚举范围为 $[0, 100]$。

确定判断条件：根据题意，我们可以列出两个方程式：$5 \times x + 3 \times y + \frac{z}{3} = 100$，$x + y + z = 100$。在枚举 $x$、$y$、$z$ 的过程中，我们可以根据这两个方程式来判断是否当前状态是否满足题意。

一一枚举可能的情况，并验证是否是问题的解。

根据枚举对象、枚举范围和判断条件，我们可以顺利写出对应的代码。

考虑提高枚举算法的效率。

在上面的代码中，我们枚举了 $x$、$y$、$z$，但其实根据方程式 $x + y + z = 100$，得知：$z$ 可以通过 $z = 100 - x - y$ 而得到，这样我们就不用再枚举 $z$ 了。

在上面的代码中，对 $x$、$y$ 的枚举范围是 $[0, 100]$，但其实如果所有钱用来买公鸡，最多只能买 $20$ 只，同理，全用来买母鸡，最多只能买 $33$ 只。所以对 $x$ 的枚举范围可改为 $[0, 20]$，$y$ 的枚举范围可改为 $[0, 33]$。

3.1.1 题目链接

1. 两数之和 - 力扣（LeetCode）

3.1.2 题目大意

描述：给定一个整数数组 nums 和一个整数目标值 target。

要求：在该数组中找出和为 target 的两个整数，并输出这两个整数的下标。可以按任意顺序返回答案。

说明：

$2 \le nums.length \le 10^4$。

$-10^9 \le nums[i] \le 10^9$。

$-10^9 \le target \le 10^9$。

只会存在一个有效答案。

示例：

示例 1：

示例 2：

3.1.3 解题思路

这里说下枚举算法的解题思路。

思路 1：枚举算法

使用两重循环枚举数组中每一个数 nums[i]、nums[j]，判断所有的 nums[i] + nums[j] 是否等于 target。

如果出现 nums[i] + nums[j] == target，则说明数组中存在和为 target 的两个整数，将两个整数的下标 i、j 输出即可。

思路 1：代码

思路 1：复杂度分析

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$。

3.2.1 题目链接

204. 计数质数 - 力扣（LeetCode）

3.2.2 题目大意

描述：给定 一个非负整数 $n$。

要求：统计小于 $n$ 的质数数量。

说明：

$0 \le n \le 5 * 10^6$。

示例：

示例 1：

示例 2：

3.2.3 解题思路

这里说下枚举算法的解题思路（注意：提交会超时，只是讲解一下枚举算法的思路）。

思路 1：枚举算法（超时）

对于小于 $n$ 的每一个数 $x$，我们可以枚举区间 $[2, x - 1]$ 上的数是否是 $x$ 的因数，即是否存在能被 $x$ 整数的数。如果存在，则该数 $x$ 不是质数。如果不存在，则该数 $x$ 是质数。

这样我们就可以通过枚举 $[2, n - 1]$ 上的所有数 $x$，并判断 $x$ 是否为质数。

在遍历枚举的同时，我们维护一个用于统计小于 $n$ 的质数数量的变量 cnt。如果符合要求，则将计数 cnt 加 $1$。最终返回该数目作为答案。

考虑到如果 $i$ 是 $x$ 的因数，则 $\frac{x}{i}$ 也必然是 $x$ 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 $x$ 是否为质数时，只需要枚举 $[2, \sqrt x]$ 中的所有数即可。

利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$，检查 $n$ 个数的整体时间复杂度为 $O(n \sqrt{n})$。

思路 1：代码

思路 1：复杂度分析

时间复杂度：$O(n \times \sqrt{n})$。

空间复杂度：$O(1)$。

3.3.1 题目链接

1925. 统计平方和三元组的数目 - 力扣（LeetCode）

3.3.2 题目大意

描述：给你一个整数 $n$。

要求：请你返回满足 $1 \le a, b, c \le n$ 的平方和三元组的数目。

说明：

平方和三元组：指的是满足 $a^2 + b^2 = c^2$ 的整数三元组 $(a, b, c)$。

$1 \le n \le 250$。

示例：

示例 1：

示例 2：

3.3.3 解题思路

思路 1：枚举算法

我们可以在 $[1, n]$ 区间中枚举整数三元组 $(a, b, c)$ 中的 $a$ 和 $b$。然后判断 $a^2 + b^2$ 是否小于等于 $n$，并且是完全平方数。

在遍历枚举的同时，我们维护一个用于统计平方和三元组数目的变量 cnt。如果符合要求，则将计数 cnt 加 $1$。最终，我们返回该数目作为答案。

利用枚举算法统计平方和三元组数目的时间复杂度为 $O(n^2)$。

注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于 $1$，所以我们可以用 $\sqrt{a^2 + b^2 + 1}$ 来代替 $\sqrt{a^2 + b^2}$。

思路 1：代码