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 | |
1 2 3 4 | |
1 2 3 | |
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 | |
1 2 3 4 5 | |
1 2 3 4 | |
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 | |
1 2 3 4 5 6 | |
1 2 3 4 5 6 | |
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
-
See bucket sort, the majority element problem, and an explanation of the bucket data structure on Stack Overflow. ↩
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Early0v0, frank-xjh, Great-designer, ksyx, qiqistyle, Tiphereth-A, Saisyc, shuzhouliu, Xeonacid, xyf007, Ir1d, HeRaNO, Planet6174, 24OI-bot, NachtgeistW, Enter-tainer, iamtwz, sshwy, tinjyu, CamberLoid, hoseahsu, CCXXXI, Menci, LeiJinpeng, shawlleyw, Ciutto, he-zhiyuan, TrickEye, c-forrest, ScrapW (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.