Brute Force and Enumeration

Brute force means listing every candidate answer and checking each one. It is rarely the final solution, but it is the right first step in an interview: it proves you understand the problem, gives you a correctness oracle for testing, and often turns into the optimal solution once you cut the search space.

Intuition

Every enumeration answers three questions:

1. What is the solution space? Pairs of indices, subsets, permutations, start and end positions of a subarray, a value in a range. Write down its size: n^2 pairs, 2^n subsets, n! orderings.
2. What can be skipped? Symmetric duplicates, candidates that can never be valid, values outside the feasible range.
3. In which order? If you want the largest valid value, enumerate from the top and stop at the first hit.

The most powerful reduction is to enumerate fewer variables. If a condition involves two unknowns and fixing one determines the other, enumerate only the first and look the second up in a hash map instead of looping over it. That one idea turns most O(n^2) pair problems into O(n).

When to use it in interviews / OAs

• Small constraints: n ≤ 8 to 10 suggests permutations, n ≤ 20 suggests subsets, n ≤ 500 suggests O(n^3) over triples or intervals.
• The answer comes from a small set: 26 letters, 10 digits, a handful of candidate values, the divisors of a number.
• Problems asking to "count pairs / triplets with a property": enumerate one element (often the middle one) and count the matching partners.
• Grid toggling puzzles where choosing one row forces everything else.
• As a reference implementation to cross-check an optimized solution on random small inputs.

Template

Fix one variable, look up the other

Counting index pairs i < j with nums[i] + nums[j] == target: the brute force tries all pairs in O(n^2). Fixing j determines the partner value target - nums[j], so a dictionary of counts of earlier values answers the question in O(1):

from collections import defaultdict


def count_pairs(nums: list[int], target: int) -> int:
    """Number of index pairs i < j with nums[i] + nums[j] == target."""
    seen: defaultdict[int, int] = defaultdict(int)  # value -> how many times seen so far
    pairs = 0
    for x in nums:
        pairs += seen[target - x]  # every earlier partner forms a pair with x
        seen[x] += 1
    return pairs

Counting only partners to the left also removes the symmetric duplicates (i, j) and (j, i) and never pairs an element with itself.

Enumerate all subsets with a bit mask

For n up to about 20, each integer mask in [0, 2^n) encodes one subset: bit i is set when element i is chosen.

def subsets_with_sum(nums: list[int], target: int) -> list[list[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):
        chosen = [nums[i] for i in range(n) if mask >> i & 1]
        if sum(chosen) == target:
            result.append(chosen)
    return result

In Python, itertools.combinations, itertools.permutations and itertools.product cover most other spaces without hand-written loops.

Shrink the range

Divisors come in pairs (d, n // d), so enumerating d up to sqrt(n) finds all of them:

from math import isqrt


def divisors(n: int) -> list[int]:
    small, large = [], []
    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            small.append(d)
            if d != n // d:  # avoid listing a square root twice
                large.append(n // d)
    return small + large[::-1]

Enumerate a small part, force the rest

In the classic lights-out puzzle, pressing a cell toggles it and its four neighbors, and the goal is to turn every light off with the fewest presses. Pressing the same cell twice cancels out, so each cell is pressed at most once. Once the presses in row 0 are fixed, a light still on in row r - 1 can only be fixed by pressing the cell directly below it, so every later row is forced. Enumerate only the 2^cols choices for the first row:

def min_presses(grid: list[list[int]]) -> int:
    """Fewest presses to turn every light off, or -1 if impossible."""
    rows, cols = len(grid), len(grid[0])
    best = -1
    for first in range(1 << cols):
        g = [row[:] for row in grid]
        presses = 0
        for r in range(rows):
            for c in range(cols):
                must_press = (first >> c & 1) if r == 0 else g[r - 1][c]
                if must_press:
                    presses += 1
                    for dr, dc in ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols:
                            g[nr][nc] ^= 1
        if not any(g[-1]) and (best == -1 or presses < best):
            best = presses
    return best

Rows above the last are guaranteed dark by construction, so only the last row needs checking.

Complexity

• count_pairs: O(n) time and O(n) space, down from O(n^2) time.
• subsets_with_sum: O(n * 2^n) time.
• divisors: O(sqrt(n)) time.
• min_presses: O(2^cols * rows * cols) time instead of O(2^(rows * cols)); enumerate along the shorter side.

Common pitfalls

• Not counting the space before coding. 2^20 is about 10^6 (fine), 2^30 is about 10^9 (too slow), and 12! is about 4.8 * 10^8 (too slow in Python).
• Ordered versus unordered pairs: decide whether (i, j) and (j, i) are different answers, and whether i may equal j.
• Duplicates in the input: a set of seen values loses multiplicities; use a count map when the problem counts index pairs.
• Building new lists inside the hottest loop. Slicing and copying multiply the cost by n.
• Forgetting the early exit when enumerating in "best first" order.
• Enumerating floating-point values. Enumerate integers or the discrete candidates instead.

Interview variations

• Two Sum family: fix one element, look up the complement; Three Sum fixes one element and runs two pointers on the sorted rest.
• Fix the middle: count triplets i < j < k by fixing j and multiplying the number of valid choices on the left and on the right.
• Enumerate the answer value: when the answer is one of few values (number of distinct letters from 1 to 26, a digit, a length), try each and solve an easier fixed-value problem, often with a sliding window.
• Enumerate boundaries plus prefix sums: all subarrays or all sub-rectangles in O(n^2) or O(n^3) with O(1) range sums.
• Fix the first row or first element: toggling grids, circular arrangements where the first choice forces the rest.
• Brute force as an oracle: write it in two minutes, then compare it against your fast solution on random small inputs.