Skip to content

Enumeration

This page briefly introduces enumeration.

Overview

Enumeration is a problem-solving strategy that guesses the answer from what is already known.

The idea is to keep guessing: try the candidates one by one, and check each against the conditions of the problem.

Key points

Define the solution space

Build a concise mathematical model.

Before you enumerate, be clear about what the possible cases are and which quantities you have to enumerate.

Shrink the enumeration space

What is the range of the enumeration? Does everything in it really have to be enumerated?

Settle these two questions whenever you solve a problem by enumeration; otherwise you will waste time.

Choose a suitable enumeration order

This depends on the problem. For example, if the problem asks for the largest prime that satisfies some condition, it is natural to enumerate from large to small.

Example problems

The following example solves a problem by enumeration and then narrows the range that is enumerated.

Example

You are given an array whose elements are pairwise distinct and nonzero. Count the ordered pairs of elements whose sum is \(0\).

Approach

Code that enumerates both numbers is easy 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 let us narrow the range. If \((a_i,a_j)\) satisfies the condition, so does \((a_j,a_i)\); and since no element is \(0\), a pair that satisfies it must have \(i\ne j\). So it is enough to enumerate \(j<i\), which counts every unordered pair once, and then multiply the result by \(2\) to get the number of ordered pairs:

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;

The range of \(j\) is now smaller, so the code does less work.

We can go further.

Do both numbers really have to be enumerated? Once one of them is fixed, the condition of the problem determines what the other one must be. If we can check directly whether that number exists, we save the time spent enumerating the second number. A more advanced technique, when the constraints allow it, is to record the numbers seen so far in buckets1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <cstring>
constexpr int MAXN = 100000;  // here MAXN is a bound on the array elements

int solve(int n, int a[]) {
  bool met[MAXN * 2 + 1];  // create buckets that can hold [-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 element we want is in a bucket, add one to the answer
    met[MAXN + a[i]] = true;  // either way, put the current element into its 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: a single pass over the array \(a\) solves the problem, so for sufficiently large \(n\) the algorithm runs in \(O(n)\).
  • Space complexity: \(O(n+\max\{|x|:x\in a\})\).

Practice problems

References and notes