Skip to content

Enumeration

This page briefly introduces the enumeration algorithm.

Introduction

Enumeration (English: Enumerate) is a problem-solving strategy based on existing knowledge to guess the answer.

The idea of enumeration is to continuously guess, trying each possibility from the set of possible candidates, and then checking whether the conditions of the problem are satisfied.

Key Points

Define the Solution Space

Establish a concise mathematical model.

When enumerating, think clearly: What are the possible cases? Which elements need to be enumerated?

Reduce the Enumeration Space

What is the range of enumeration? Is it necessary to enumerate all possibilities?

When solving problems with enumeration, always consider these two points; otherwise, unnecessary time overhead may be incurred.

Choose an Appropriate Enumeration Order

Determine based on the problem. For example, if the problem asks for the largest prime number satisfying certain conditions, it is natural to enumerate from large to small.

Example

The following is an example of using enumeration to solve a problem and optimizing the enumeration range.

Example

Given an array where all elements are distinct and none are \(0\). Find the number of pairs in the array whose sum is \(0\).

Solution

The code to enumerate two numbers is straightforward to write.

1
2
3
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

1
2
3
4
for i in range(n):
    for j in range(n):
        if a[i] + a[j] == 0:
            ans += 1

1
2
3
for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

Now consider how to optimize the enumeration range. Since the problem does not require the pairs to be ordered, the answer is twice the number of ordered pairs (consider that if (a, b) is a valid pair, then (b, a) is also valid). For this case, we can simply count the answer under the artificial requirement of order and then multiply by \(2\).

We can require the first number to appear at a later position. The code is as follows:

1
2
3
4
for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;
ans *= 2;

1
2
3
4
5
for i in range(n):
    for j in range(i):
        if a[i] + a[j] == 0:
            ans += 1
ans *= 2

1
2
3
4
for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (a[i] + a[j] == 0) ++ans;
ans *= 2;

It is not difficult to see that the enumeration range for \(j\) has been reduced, thereby decreasing the time overhead of this code.

We can further optimize on this basis.

Is it necessary to enumerate both numbers? After enumerating one number, the condition of the problem determines the condition for the other element (the other number). If we can find a method to directly check whether the required number exists, we can save the time of enumerating the second number. More advanced, when the data range allows, we can use a bucket1 to record the numbers we have traversed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <cstring>
constexpr int MAXN = 100000;  // Here MAXN is the bound for the number of elements in the array

int solve(int n, int a[]) {
  bool met[MAXN * 2 + 1];  // Create a bucket that can hold values in the range [-MAXN, MAXN]
  memset(met, 0, sizeof(met));
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (met[MAXN - a[i]]) ++ans;  // If the bucket contains the desired element, increment the answer
    met[MAXN + a[i]] = true;  // In any case, put the current element into the bucket
  }
  return ans * 2;
}

1
2
3
4
5
6
met = [False] * (MAXN * 2 + 1)
for i in range(n):
    if met[MAXN - a[i]]:
        ans += 1
    met[a[i] + MAXN] = True
ans *= 2

1
2
3
4
5
6
boolean[] met = new boolean[MAXN * 2 + 1];
for (int i = 0; i < n; ++i) {
    if (met[MAXN - a[i]]) ++ans;
    met[MAXN + a[i]] = true;
}
ans *= 2;

Complexity Analysis

  • Time Complexity Analysis: Traversing the \(a\) array once is sufficient to meet the problem requirements. When \(n\) is sufficiently large, the time complexity is \(O(n)\).
  • Space Complexity Analysis: \(O(n+\max\{|x|:x\in a\})\).

Exercises

Footnotes

  1. Bucket Sort, Majority Element Problem, and Explanation of Bucket Data Structure on Stack Overflow (English) ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用