Basics 0/97

Complete search: enumerating candidate solutions · 1 of 3

Complete search technique

Recognise a complete search, write one over every pair, and count its candidates against the time limit before writing code.

1,515 words · 7 min read

Part 1 of 4 Complete search

Try every candidate

Many problems can be solved by trying every possibility. When the answer is a pair of values, the program looks at every pair. When it is a group of items, or an order to put them in, the program looks at every group or every order. It checks each possibility against the statement and keeps what the problem asks for: how many of them pass, the best one, or any one that passes.

This method is called complete search, or brute force, and each possibility it tries is a candidate. It is the first method to consider for a problem, in a contest and in an interview, because the program is short and it is easy to see that it is correct. It tries every candidate, including those that look hopeless, so it cannot miss the answer, and it can be made faster later, once its answers are right. Its weakness is speed: the number of candidates can be enormous, so before writing a complete search we count them.

As a first example, take the five numbers below. We want to know how many pairs of them add up to 12.

A candidate is a pair of positions. To list every pair once, we take each value in turn and pair it with each value to its right:

Every pair of the five numbers, with its sum
First valuePaired withSums
49, 8, 3, 513, 12, 7, 9
98, 3, 517, 12, 14
83, 511, 13
358

The five numbers have 4+3+2+1=104 + 3 + 2 + 1 = 10 pairs, and two of them add up to 12: 4+84 + 8 and 9+39 + 3. There is no third, and we can be sure of it because the table holds every pair.

Two loops over the positions

The program follows the table. The outer loop picks the first position i, and the inner loop picks the second position j from the positions after i:

Sign up to run
def count_pairs(nums, target):
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                count += 1
    return count

print(count_pairs([4, 9, 8, 3, 5], 12))

It prints 2. The inner loop starts at i + 1 so that no value is paired with itself and each pair is visited once, with i to the left of j. If the inner loop ran over every position other than i, the pair of 4 and 8 would be found at positions 0 and 2 and again at positions 2 and 0, and the program would print 4.

Visiting a candidate twice does no harm when the search keeps a maximum or a minimum. When it counts, as here, every candidate has to be listed exactly once.