Enumeration

Topic type: Technique-Based
LeetCode tag size: ~70 problems → depth: core algorithms, main patterns, key complexities

Enumeration here means the technique of iterating over a well-defined candidate set (pairs, triplets, divisors, subsets of size k, complement values) and checking each candidate against a condition. Contrast with Backtracking (undo/restore state, tree-shaped search) and Brute Force (unguided exhaustion). Enumeration problems typically reduce to "pick the right candidate space, then shrink it."

---

Core Concepts

Candidate set — the collection of all items to be tested. The key insight in enumeration is choosing the tightest candidate set that is still guaranteed to contain the answer; a suboptimal choice inflates time complexity without improving correctness.

Fix-and-iterate — fix one element (or index, or value) and enumerate choices for the rest relative to that anchor. This is the structural basis of all enumeration: an O(n²) pair search fixes one endpoint and iterates the other; an O(n³) triplet search fixes two.

Complement search — instead of enumerating both elements of a pair (a, b) that satisfy f(a, b) = target, fix a and derive the required b = g(a, target), then test whether b exists. Reduces a nested loop to a single loop + lookup.

Divisor enumeration — iterate from 1 to √n to find all divisors of n; each divisor d yields a pair (d, n/d). Finding all divisors of n costs O(√n). Finding all divisors of all numbers up to N costs O(N log N) via a sieve-like pass.

Value-space vs. index-space enumeration — index-space iterates over positions in the input; value-space iterates over values in a range [lo, hi] independently of where those values appear. Problems with a bounded value range often permit value-space enumeration when index-space would be too slow.

Pruning — discarding candidates without evaluating them by proving they cannot satisfy the condition. Sorting the input before enumeration enables early termination and skip-equal-elements pruning without sacrificing correctness.

---

Types / Variants

For bitmask-based subset enumeration when n ≤ 20, see bitmask.md.
For backtracking-driven enumeration with undo/restore, see backtracking.md.
For mathematical enumeration of combinatorial structures, see combinatorics.md.

---

Key Algorithms

Pair Enumeration (Nested Loop)

Iterate all ordered or unordered pairs from an array or string. For unordered pairs: outer loop i from 0 to n−2, inner loop j from i+1 to n−1. For ordered pairs: both loops run over [0, n). O(n²) time, O(1) extra space. Acceptable for n ≤ 3000; too slow for n > 10⁴.

Use when no algebraic relationship between a pair's two elements allows complement lookup, and when the predicate cannot be reformulated as a prefix or sliding-window condition.

Two-Sum Complement Lookup

Fix element a; the required partner b = target − a. Query b in a hash set built from the array. O(n) time, O(n) space. The hash set can be built incrementally (left to right) to avoid counting an element paired with itself.

seen = {}
for i, x in enumerate(nums):
    if target - x in seen: return [seen[target - x], i]
    seen[x] = i

Generalises to any two-variable target: fix one, derive the other, look up. Works for sum, XOR, GCD, bitwise-OR targets.

Triplet Enumeration with Two Pointers

Sort the array. Fix index i (the smallest element). Use two pointers lo = i+1, hi = n−1 to find pairs summing to −nums[i]. Move lo right (sum too small) or hi left (sum too large); skip duplicates at both pointers. O(n²) time after O(n log n) sort. Standard for 3Sum and variants.

nums.sort()
for i in range(len(nums) - 2):
    lo, hi = i + 1, len(nums) - 1
    while lo < hi: ...  # two-pointer scan

Pruning: if nums[i] > 0, all remaining triplets sum to positive — break early.

Divisor Enumeration up to √n

For a given n, iterate d from 1 to √n; if n % d == 0, record both d and n//d (deduplicate when d == n//d). O(√n) per number.

divs = []
d = 1
while d * d <= n:
    if n % d == 0: divs += [d] if d*d == n else [d, n//d]
    d += 1

Multiples Sieve (Divisors of All Numbers up to N)

For each d from 1 to N, add d to the divisor list of every multiple k·d ≤ N. O(N log N) total (harmonic series). Useful when a problem asks about divisors of many numbers simultaneously rather than a single n.

Split-Point Enumeration

Iterate every position i from 0 to n−1 as a split boundary; evaluate the left part [0, i] and right part [i+1, n−1]. If evaluating each part is O(1) with preprocessing (prefix arrays), total cost is O(n). Without preprocessing each evaluation is O(n), giving O(n²). Always pair with a prefix/suffix precomputation step.

Permutation Enumeration

Enumerate all k! orderings of k ≤ 8 elements. In Python, use itertools.permutations(items) for cleanliness. For custom generation (e.g., pruning mid-permutation), use a backtracking skeleton with a visited array; see backtracking.md.

Value-Space Enumeration

When the answer lies in a bounded integer range [lo, hi] and checking a given value is O(f(n)), iterate every candidate value and check. Common when the value range is small (≤ 10⁶) and checking is O(1) or O(log n). Replaces a search over input indices with a sweep over the value domain.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Self-pairing in complement lookup. When searching for a pair (a, b) where a ≠ b, inserting a into the hash map before querying the complement of the next element can match an element with itself. Fix: either insert after querying, or track indices and reject i == j.

• Duplicate pairs / triplets counted multiple times. Without skip-duplicate logic, sorted arrays with repeated values produce the same logical pair from different index positions. After sorting, skip nums[i] if i > start and nums[i] == nums[i-1] at every loop level independently.

• Divisor enumeration boundary (d × d == n). When d = √n exactly, n/d == d, so the divisor d should be added only once. Forgetting the deduplication yields a duplicate divisor; the check d*d == n handles it.

• Integer overflow in pair-sum comparisons. When values are up to 10⁹ and the target is a sum of two, the intermediate sum can reach 2×10⁹ which overflows a 32-bit int. In Python this is not an issue; in Java/C++ use long.

• Value-space sweep on a range that starts at 0 vs. 1. Off-by-one on the enumeration bounds misses valid candidates. Confirm whether the problem includes 0 and whether the range is closed or half-open.

• Split-point enumeration with empty parts. Splitting at position 0 or n leaves an empty substring on one side. If empty substrings are invalid, start the split-point loop at i = 1 and end at i = n−1, not i = 0 or i = n.

• Two-pointer not resetting after fixing a new anchor. In triplet enumeration, when the outer loop advances i, the inner two pointers must reset to lo = i+1, hi = n−1. Carrying over stale pointer positions from the previous iteration produces incorrect results.

• Permutation enumeration applying to only k < n items. itertools.permutations(items, k) enumerates ordered k-selections, not all n! permutations. Using the wrong k silently yields fewer or more candidates than expected.

• Assuming complement existence implies a valid answer. In complement lookup, the complement value must also satisfy index constraints (e.g., different index, earlier index). Check these constraints explicitly after the lookup.

---

Implementation Notes

• Python itertools.combinations(range(n), 2) generates all unordered pairs without a nested loop; use for clarity on small n, but a manual nested loop is faster in practice for n > 200.
• itertools.permutations(items) is faster than a manual backtracking loop for pure enumeration (no pruning); if mid-permutation pruning is needed, write the backtracking loop instead.
• For complement lookup, collections.Counter builds a frequency map in one line; decrement the count of the anchor element before querying to handle duplicates.
• Divisor enumeration in Python: int(n**0.5) can be off by one due to floating-point error; use while d*d <= n (integer comparison) rather than range(1, int(n**0.5)+1).
• For multiples sieve, range(d, N+1, d) iterates all multiples of d up to N; this is the canonical Python idiom and does not require explicit index arithmetic.
• When enumerating split points in a string, precompute a palindrome table or prefix-hash array before the loop; recomputing per split is O(n) per step and inflates to O(n²) total.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Pair enumeration / complement lookup

• Two Sum (LC 1) — complement lookup, hash map
• Two Sum II – Input Array Is Sorted (LC 167) — two-pointer pair enumeration
• Count Number of Pairs With Absolute Difference K (LC 2006) — complement lookup
• Number of Pairs of Strings With Concatenation Equal to Target (LC 2023)

Triplet enumeration

• 3Sum (LC 15) — sort + fix one + two pointers; canonical triplet problem
• 3Sum Closest (LC 16) — same structure, track minimum delta
• Count Good Triplets (LC 1534) — brute-force O(n³) acceptable for n ≤ 100

Divisor / factor enumeration

• Count Primes (LC 204) — sieve of Eratosthenes (multiples sieve)
• Three Divisors (LC 1952) — divisor count to √n
• Minimum Number of Days to Make m Bouquets (LC 1482) — value-space binary search; divisor logic in check
• Find All Divisors of a Number (common sub-problem in many medium problems)

Split-point / interval enumeration

• Partition Array for Maximum Sum (LC 1043) — split-point DP; enumerate partition lengths
• Check if String Is Decomposable Into Value-Equal Substrings (LC 1933)
• Count Ways to Split Array Into Three Subarrays (LC 1712) — two split points; prefix sum for O(1) evaluation

Value-space enumeration

• Find the Difference of Two Arrays (LC 2215) — sweep value space via sets
• Count Integers in Ranges (LC 2554 / 2273)
• Ugly Number II (LC 264) — enumerate candidate multiples in value space (min-heap approach)

Permutation / small-set enumeration

• Next Permutation (LC 31) — one-step permutation navigation
• Permutations (LC 46) — enumerate all n! orderings (n ≤ 8)
• Minimum Time Difference (LC 539) — enumerate all pairs of sorted times

Clarification Questions to Ask

• What is the size of n? This determines whether O(n²) pair enumeration is feasible (n ≤ 3000), O(n³) triplet enumeration (n ≤ 200), or whether a smarter approach is required.
• What is the value range of elements? A bounded value range may permit value-space enumeration even when n is large.
• Are duplicate elements present? Determines whether skip-duplicate logic is needed.
• Is the answer a count (mod p?) or the actual pair/triplet/set? Counts can sometimes be derived without full enumeration.
• For divisor problems: is n a single number or a range [1, N]? Single → √n; range → sieve.
• Are indices important (e.g., i < j required) or just values? Affects whether the hash map should track index or just existence.

Common Interview Mistakes

• Using O(n²) pair enumeration when a complement lookup with a hash map gives O(n) — interviewers expect the hash map approach for two-sum variants.
• Forgetting to skip duplicate elements after sorting in triplet enumeration, producing duplicate triplets in the output.
• Iterating d from 1 to n instead of √n for divisor enumeration — O(n) instead of O(√n) per number.
• Not resetting the two pointers (lo, hi) after advancing the outer fix-one index in triplet search.
• Inserting into the complement hash map before querying, allowing an element to pair with itself.
• Using floating-point int(n**0.5) as the upper bound of divisor enumeration and missing the exact square root due to floating-point rounding.

Typical Follow-Up Escalations

• "Now find all such pairs, not just one." → Return a list; use the same O(n) complement-lookup loop and append matches.
• "Now the array has duplicates; count pairs by value, not index." → Use Counter; for pair (a, b) with a ≠ b, contribution is count[a] * count[b]; for a == b, contribution is count[a] * (count[a]-1) / 2.
• "Now find the count of triplets, not list them." → After the sort + fix-one step, the two-pointer inner pass can count matching pairs in O(1) per move instead of recording them.
• "Now do it in O(n log n)." → Sort + binary search replaces the O(n) inner two-pointer with O(log n) per anchor; overall still O(n log n).
• "n is up to 10⁵; O(n²) won't work." → Reformulate as a complement lookup, frequency map, or prefix-based technique; two-pointer is O(n) after sorting.
• "What if the target changes per query?" → Preprocess a sorted list or frequency map once; answer each query in O(n) (two-pointer re-scan) or O(n log n) (binary search per element).