Complete Search

The idea

If the number of possible answers is small enough, check them all. This is complete search, also called brute force, and it solves a large fraction of entry-level problems.

It is not a fallback for when you cannot find something better. When the constraints permit it, it is the intended solution — it is easier to write correctly and easier to reason about than a clever alternative.

Deciding whether it fits

Count the possibilities, multiply by the work per possibility, and compare against roughly 10⁸ operations.

Search space sizes

Read the constraint, find the matching row, and you know whether to write the loops. A problem with N ≤ 20 and a yes/no answer about subsets is telling you to enumerate subsets.

Nested loops over pairs and triples

The most common form. Fix each combination and evaluate it.

Given N integers, find the largest sum of two distinct elements.

int best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        best = Math.max(best, a[i] + a[j]);
    }
}
System.out.println(best);

Starting the inner loop at i + 1 rather than 0 does two things: it avoids pairing an element with itself, and it visits each unordered pair exactly once instead of twice.

Initializing best to Integer.MIN_VALUE rather than 0 matters when all values are negative. Initializing an accumulator to a value that could be the answer is a recurring bug.

Enumerating subsets with bitmasks

When each of N items is either chosen or not, there are 2^N combinations, and each maps to the bits of an integer.

Given N ≤ 20 weights, is there a subset summing to exactly target?

boolean possible = false;
for (int mask = 0; mask < (1 << n); mask++) {
    long sum = 0;
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            sum += w[i];
        }
    }
    if (sum == target) {
        possible = true;
        break;
    }
}

1 << n is 2ⁿ. Bit i of mask being set means item i is in the subset. The test (mask & (1 << i)) != 0 checks that bit.

Searching over the answer

Sometimes the thing to enumerate is not a subset of the input but the answer itself.

Cows are at given positions. Find the smallest integer position p such that the total distance from all cows to p is at most D.

If coordinates go up to 1,000, try every one:

int answer = -1;
for (int p = 0; p <= 1000; p++) {
    long total = 0;
    for (int i = 0; i < n; i++) {
        total += Math.abs(a[i] - p);
    }
    if (total <= d) {
        answer = p;
        break;
    }
}

This is O(range · N). It works because the coordinate range is small. When the range is large but the property is monotonic — once true, always true — binary search replaces the outer loop. That is covered in Binary Search.

Permutations

When you need every ordering of N ≤ 10 items, generate permutations recursively. The general technique is covered in Recursive Complete Search; for small fixed sizes, nested loops with distinctness checks are simpler:

// every ordered triple of distinct indices
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            if (i != j && j != k && i != k) {
                // evaluate the arrangement (i, j, k)
            }

Pruning

Stopping early when a partial choice already cannot work often turns an infeasible search into a fast one. The complexity does not change on paper, but the practical runtime can drop by orders of magnitude.

for (int mask = 0; mask < (1 << n); mask++) {
    long sum = 0;
    boolean over = false;
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            sum += w[i];
            if (sum > target) { over = true; break; }   // no point continuing
        }
    }
    if (!over && sum == target) { /* ... */ }
}

Pruning only helps if the condition genuinely rules out the rest of the branch. Adding a check that is almost never true costs time instead of saving it.

Next