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:
| First value | Paired with | Sums |
|---|---|---|
| 4 | 9, 8, 3, 5 | 13, 12, 7, 9 |
| 9 | 8, 3, 5 | 17, 12, 14 |
| 8 | 3, 5 | 11, 13 |
| 3 | 5 | 8 |
The five numbers have pairs, and two of them add up to 12: and . 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:
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.
Correctness and cost
A complete search has two parts: the loops that list the candidates, and the check applied to each one. Its answer is right when two things hold: every possible answer is among the candidates, and the check tests exactly what the statement asks. In the example both are easy to confirm: the loops reach every pair of positions, and the check is the sum from the question.
Its running time is the number of candidates multiplied by the cost of checking one:
The check here is one addition and one comparison. To count the candidates, pick the first position of a pair in ways and the second in ways, since it must differ from the first. That makes choices, but each pair is among them twice, once in each order, so values have pairs. A loop written in Python runs roughly simple operations a second, and at that rate the same program is fast or hopeless depending on :
Five thousand values took 0.3 seconds when we ran the program, a little faster than the rough rate predicts. Two hundred thousand make 1,600 times as many pairs, about eight minutes of work. That is why CSES Sum of Two Values, which allows 200,000 values and one second, is solved with a sort and a single pass instead.
Pairs, subsets and orderings
Three kinds of candidate come up again and again:
- A fixed number of choices, such as the two positions of a pair or the three of a triple. These come from nested loops, one loop for each choice, as in the example.
- A subset is a group of the items, of any size. Only membership matters: for the items a, b and c, the group of a and c is one subset, whichever of the two we name first.
- An ordering, also called a permutation, lists every item once, so two orderings of the same items differ only in the order. The three items have six orderings: abc, acb, bac, bca, cab and cba.
A subset makes one choice for each item, in or out, so items have subsets. An ordering can start with any of the items, continue with any of the that remain, and so on down to the last item, so items have orderings. For a, b and c that makes 8 subsets and the 6 orderings above.
The number of candidates of each kind
- Every pair
- for . Fits in a second up to about .
- Every subset
- for and for . Fits up to about .
- Every ordering
- for and about for . Fits up to about .
Each count still has to be multiplied by the cost of one check, and a check often takes about steps, such as adding up the items of a subset. For subsets that makes steps at and at , so a search over subsets fits in a second up to about . For orderings it makes steps at and at , so a search over orderings fits up to about . These bounds assume the C++ rate of about simple operations a second. At the of a Python loop they drop to about 18 for subsets and 9 for orderings.
Read the other way round, these bounds hint at the intended solution: a statement that allows at most 20 items leaves room for a search over every subset, and one that allows at most 8 or 10 leaves room for a search over every ordering.
Candidate counts and the one-second budget
The demo opens at . Read the bars for and there, then press the preset 10. At 20 only the subsets fit in the budget, and at 10 the orderings fit as well.
The other three pages of this lesson take these searches in turn:
- Brute force is about searches written as nested loops, and how to choose what the loops run over.
- Subsets and permutations shows how to loop over every subset and every ordering.
- Meet in the middle, an advanced page, extends a search over subsets from 20 items to 40.
Common mistakes
Starting the inner loop at
i.- Where it breaks
- On
[6, 4, 9]with the target 12, the program pairs the 6 with itself and prints 1, although no two of the three numbers add up to 12. - The fix
- Start the inner loop at
i + 1, so that a pair always has two different positions.
Reading a small limit as room for any search.
- Where it breaks
- With , a search over every ordering has candidates, more than 700 years of work even at operations a second, although the subsets take a fraction of a second.
- The fix
- Decide which kind of candidate the search lists, count the candidates for the largest input, and multiply by the cost of one check.
Recall One problem asks for the best order in which to do n ≤ 9 tasks, another for the best group of n ≤ 18 items. How many candidates does a complete search have in each, and does it fit in a second?
The first has orderings and the second subsets. With a check of 9 or 18 steps for each candidate, the work is about and operations, far below , so both fit.