Brute force 0/1

Lesson 16 of 21

Brute force

Try every candidate, and count the work against the time limit first.

Part 1 of 9 Try every candidate

Answering by trying every candidate

Take the numbers 3, 8, 1 and 6, and look for two that add up to 9. Four numbers make only six pairs, so you can check them all by hand: 3 + 8, 3 + 1, 3 + 6, 8 + 1, 8 + 6 and 1 + 6. Two of the sums are 9, 3 + 6 and 8 + 1.

Many problems can be solved the same way. Counting the ways three sticks can form a triangle, or the ways to pay 100 yen with the coins in your pocket, comes down to a list of possible answers you could write out one at a time. Each possible answer is a candidate. Trying every candidate and checking it is called brute force, or complete search.

So far your loops have visited each element of a list once. To check every pair, a program needs a loop that visits every pair, and other problems need every triple or every combination of a few choices. In this lesson we write those loops, and we work out, before writing one, whether it will finish within the time limit.

Definition

A brute force solution tries every candidate answer, checks each one, and keeps the ones that pass.