Enumeration

In this article, we will introduce enumeration—a strategy that solves problems by guessing answers based on existing knowledge. Essentially, enumeration means trying out each candidate in a set of possibilities and then checking if that candidate meets the specified conditions.

Introduction

Enumeration (from the word “enumerate”) is a method where you systematically try every possible option until you find the correct answer. It’s a straightforward strategy, but it requires careful planning to manage the number of options you need to check.

Key Points

1. Determine the Solution Space

Before you start coding, build a clear mathematical model of the problem. Ask yourself:

• What are the possible cases?
• Which elements need to be enumerated?

Creating a concise model helps you understand exactly what to try during enumeration.

2. Reduce the Search Space

You should carefully think about the range of values to consider. Do you really need to go through every option? Narrowing your search space is essential to avoid unnecessary computational work.

3. Choose a Suitable Enumeration Order

Depending on the problem, the order in which you check possibilities can make a big difference. For example, if the task is to find the largest prime that meets certain criteria, beginning your search from the largest values might be more efficient.

Example: Counting Pairs that Sum to Zero

Consider this problem: Given an array of distinct numbers, count the number of pairs whose sum is zero.

A straightforward approach is to check every possible pair. For example:

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

However, notice that each valid pair is counted twice because if (a, b) is a valid pair, then (b, a) will also be counted. We can avoid this redundancy by ensuring we only count each pair once, such as by enforcing an order on the indices:

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

This small change limits the inner loop’s range and reduces the overall number of checks, thus saving time.

Further Optimization

Is it necessary to explicitly check both numbers in a pair? Often, determining one number completely specifies what the other number must be. If you can quickly check whether the required partner exists, you can eliminate the inner loop entirely.

In problems where the data range permits, you can use a bucket (a frequency or presence array) to record which numbers have already been seen. For example:

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

In the code above, the bucket helps us quickly determine if the counterpart of the current number (so that their sum equals zero) has been encountered already. This optimization reduces the time complexity significantly.

Complexity Analysis

• Time Complexity: The optimized approach only needs a single pass through the array, achieving a time complexity of

  $$O(n)$$

  when n is large.

• Space Complexity: The extra space used depends on the range of the input values, approximately $O(n + \max\{|x|: x \in a\}).$

Exercises

Try tackling the following challenge:

• Write an algorithm to solve the "Lights Out Problem" using enumeration and optimized search techniques.

By applying these enumeration strategies and optimizations, you can design algorithms that efficiently explore the solution space while avoiding unnecessary computations. Happy coding!