枚举算法（Enumeration Algorithm）：也称为穷举算法，指的是按照问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中，既不能遗漏也不能重复。
枚举算法是设计最简单、最基本的搜索算法，其核心思想是通过列举问题的所有状态，将它们逐一与目标状态进行比较，从而得到满足条件的解。
- 枚举算法的优点：
- 容易编程实现，也容易调试。
- 建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。
- 枚举算法的缺点：
- 效率比较低，不适合求解规模较大的问题。
所以，枚举算法通常用于求解问题规模比较小的问题，或者作为求解问题的一个子算法出现，通过枚举一些信息并进行保存，而这些消息的有无对主算法效率的高低有着较大影响。
采用枚举算法解题的一般思路如下：
- 确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
- 一一枚举可能的情况，并验证是否是问题的解。
- 考虑提高枚举算法的效率。
我们可以从下面几个方面考虑提高算法的效率：
- 抓住问题状态的本质，尽可能缩小问题状态空间的大小。
- 加强约束条件，缩小枚举范围。
- 根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。
- 描述：给定一个整数数组
nums和一个整数目标值target。 - 要求：在该数组中找出和为
target的两个整数，并输出这两个整数的下标。
这里说下枚举算法的解题思路。
使用两重循环枚举数组中每一个数 nums[i]、nums[j]。判断所有的 nums[i] + nums[j] 是否等于 target。
- 如果出现
nums[i] + nums[j] == target，则说明数组中存在和为target的两个整数，将两个整数的下标i、j输出即可。
利用两重循环进行枚举的时间复杂度为
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if i != j and nums[i] + nums[j] == target:
return [i, j]
return []描述：给定 一个非负整数 n。
要求：统计小于 n 的质数数量。
这里说下枚举算法的解题思路（注意：提交会超时，只是讲解一下枚举算法的思路）。
对于小于 n 的每一个数 x，我们可以枚举区间 [2, x - 1] 上的数是否是 x 的因数，即是否存在能被 x 整数的数。如果存在，则该数 x 不是质数。如果不存在，则该数 x 是质数。
这样我们就可以通过枚举 [2, n - 1] 上的所有数 x，并判断 x 是否为质数。
在遍历枚举的同时，我们维护一个用于统计小于 n 的质数数量的变量 cnt。如果符合要求，则将计数 cnt 加 1。最终返回该数目作为答案。
考虑到如果 i 是 x 的因数，则 x 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 x 是否为质数时，只需要枚举
利用枚举算法单次检查单个数的时间复杂度为 n 个数的整体时间复杂度为
class Solution:
def isPrime(self, x):
for i in range(2, int(pow(x, 0.5)) + 1):
if x % i == 0:
return False
return True
def countPrimes(self, n: int) -> int:
cnt = 0
for x in range(2, n):
if self.isPrime(x):
cnt += 1
return cnt描述：给你一个整数 n。
要求：请你返回满足
说明：
-
平方和三元组：指的是满足
$a^2 + b^2 = c^2$ 的整数三元组(a, b, c)。
枚举算法。
我们可以在 [1, n] 区间中枚举整数三元组 (a, b, c) 中的 a 和 b。然后判断 n，并且是完全平方数。
在遍历枚举的同时，我们维护一个用于统计平方和三元组数目的变量 cnt。如果符合要求，则将计数 cnt 加 1。最终，我们返回该数目作为答案。
利用枚举算法统计平方和三元组数目的时间复杂度为
- 注意：在计算中，为了防止浮点数造成的误差，并且两个相邻的完全平方正数之间的距离一定大于
1，所以我们可以用$\sqrt{a^2 + b^2 + 1}$ 来代替$\sqrt{a^2 + b^2}$ 。
class Solution:
def countTriples(self, n: int) -> int:
cnt = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
c = int(sqrt(a * a + b * b + 1))
if c <= n and a * a + b * b == c * c:
cnt += 1
return cnt先来介绍一下「子集」的概念。
-
子集：如果集合
A的任意一个元素都是集合S的元素，则称集合A是集合S的子集。可以记为$A \in S$ 。
有时候我们会遇到这样的问题：给定一个集合 S，枚举其所有可能的子集。
枚举子集的方法有很多，这里介绍一种简单有效的枚举方法：「二进制枚举子集算法」。
对于一个元素个数为 n 的集合 S 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 1 来表示选取该元素，用数字 0 来表示不选取该元素。
那么我们就可以用一个长度为 n 的二进制数来表示集合 S 或者表示 S 的子集。其中二进制的每一位数都对应了集合中某一个元素的选取状态。对于集合中第 i 个元素（i 从 0 开始编号）来说，二进制对应位置上的 1 代表该元素被选取，0 代表该元素未被选取。
举个例子来说明一下，比如长度为 5 的集合 S = {5, 4, 3, 2, 1}，我们可以用一个长度为 5 的二进制数来表示该集合。
比如二进制数 11111 就表示选取集合的第 0 位、第 1 位、第 2 位、第 3 位、第 4 位元素，也就是集合 {5, 4, 3, 2, 1} ，即集合 S 本身。如下表所示：
| 集合 S 对应位置（下标） | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|
| 二进制数对应位数 | 1 | 1 | 1 | 1 | 1 |
| 对应选取状态 | 选取 | 选取 | 选取 | 选取 | 选取 |
再比如二进制数 10101 就表示选取集合的第 0 位、第 2 位、第 5 位元素，也就是集合 {5, 3, 1}。如下表所示：
| 集合 S 对应位置（下标） | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|
| 二进制数对应位数 | 1 | 0 | 1 | 0 | 1 |
| 对应选取状态 | 选取 | 未选取 | 选取 | 未选取 | 选取 |
再比如二进制数 01001 就表示选取集合的第 0 位、第 3 位元素，也就是集合 {5, 2}。如下标所示：
| 集合 S 对应位置（下标） | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|
| 二进制数对应位数 | 0 | 1 | 0 | 0 | 1 |
| 对应选取状态 | 未选取 | 选取 | 未选取 | 未选取 | 选取 |
通过上面的例子我们可以得到启发：对于长度为 5 的集合 S 来说，我们只需要从 00000 ~ 11111 枚举一次（对应十进制为 5 的集合 S 的所有子集。
我们将上面的例子拓展到长度为 n 的集合 S。可以总结为：
- 对于长度为
5的集合S来说，只需要枚举$0 \sim 2^n - 1$ （共$2^n$ 种情况），即可得到所有的子集。
class Solution:
def subsets(self, S): # 返回集合 S 的所有子集
n = len(S) # n 为集合 S 的元素个数
sub_sets = [] # sub_sets 用于保存所有子集
for i in range(1 << n): # 枚举 0 ~ 2^n - 1
sub_set = [] # sub_set 用于保存当前子集
for j in range(n): # 枚举第 i 位元素
if i >> j & 1: # 如果第 i 为元素对应二进制位删改为 1，则表示选取该元素
sub_set.append(S[j]) # 将选取的元素加入到子集 sub_set 中
sub_sets.append(sub_set) # 将子集 sub_set 加入到所有子集数组 sub_sets 中
return sub_sets # 返回所有子集- 【书籍】算法竞赛入门经典：训练指南 - 刘汝佳，陈锋 著
- 【书籍】ACM-ICPC 程序设计系列 - 算法设计与实现 - 陈宇 吴昊 主编
- 【博文】枚举排列和枚举子集 - CUC ACM-Wiki