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.
Listing every pair with nested loops
A pair needs two positions at once: i for the first number and j for the second. Putting one for loop inside another gives both. A loop inside a loop is a nested loop. The outer loop picks i, and for each value of i the inner loop runs through all of its values of j before i moves on.
In the program below the inner loop starts at i + 1, so j is always to the right of i. Step through it on the four numbers from the opening. It counts the pairs that add up to 9, and it should print 2.
Step through the pair loop
Counting each pair once
The second preset has a single number, [5]. When i is 0, the inner loop would start at position 1, which does not exist, so it runs zero times and the program prints 0. One number makes no pair, so 0 is right.
The third preset starts j at 0 instead, on [3, 6, 3] with a target of 6. Only one pair of positions adds up to 6, the two 3s at positions 0 and 2, but the program prints 4. It counts that pair twice, once as 0 and 2 and again as 2 and 0, and it also pairs each 3 with itself, since 3 + 3 = 6. Starting j at i + 1 gives each pair of different positions exactly once, smaller position first, and with that start the program prints 1.
The number of pairs the loop checks has a formula. The first number pairs with the numbers after it, the second with , and so on down to the last, which pairs with none:
This is the same sum as the comparisons selection sort makes. For four numbers it gives , the six pairs listed by hand.
Listing every triple
A triple needs a third loop inside the second, with k starting at j + 1. Each group of three positions then comes up exactly once, in the order . Making Triangle is practice for exactly this loop: it counts the choices of three sticks with different lengths that can form a triangle.
There are sticks, and stick has length . Count the ways to choose three sticks, by position, whose lengths are all different and can form a triangle.
Constraints
Sample 1 · Input
5 4 4 9 7 5
Output
5
Sample 2 · Input
6 4 5 4 3 3 5
Output
8
Sample 3 · Input
2 1 1
Output
0
Three lengths form a triangle when each side is shorter than the other two put together. Lengths 4, 7 and 9 work, since is more than 9. Lengths 4, 5 and 9 do not: , and the two short sides lie flat along the long one.
In the first sample the sticks are 4, 4, 9, 7 and 5, and the two 4s cannot be chosen together because the lengths must differ. The sets 4, 7, 9 and 4, 5, 7 work with either 4, which makes four choices, and 5, 7, 9 is the fifth. The set 4, 5, 9 fails. The problem counts choices of sticks, so the two sticks of length 4 give two different choices.
n = int(input())
lengths = list(map(int, input().split()))
count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
a, b, c = lengths[i], lengths[j], lengths[k]
if a != b and b != c and a != c:
if a + b > c and a + c > b and b + c > a:
count += 1
print(count)Because the loops pick positions, the two sticks of length 4 are different candidates without any special handling.
Python's itertools module can write these loops for you. After from itertools import combinations, the line for a, b, c in combinations(lengths, 3): visits the same triples as the three loops, in the same order , and it also picks by position.
Will it finish in time?
Making Triangle has at most 100 sticks. A brute force is only useful if it finishes within the time limit, usually 1 or 2 seconds, so before you write one, count how many candidates it checks. The limits in the problem statement are enough to do this.
Use a rule of thumb: Python runs about simple steps a second, where a step is something like an addition, a comparison or one pass of a loop body. For Making Triangle with , the triple loop checks
Each triple takes a few comparisons, so that is around a million steps, or about 0.1 seconds.
The count grows quickly with the input. Here is the pair loop at four sizes:
| Pairs, | C++ | Python | |
|---|---|---|---|
| 100 | 4,950 | under 0.001 s | under 0.001 s |
| 1,000 | 0.005 s | 0.05 s | |
| 10,000 | 0.5 s | 5 s | |
| 100,000 | 50 s | 500 s |
Each time grows by a factor of 10, the number of pairs grows by a factor of about 100. In Python, already takes about 5 seconds, over the limit, and takes more than 8 minutes.
The same counting works backwards: from the limit on you can tell which brute force a problem allows. USACO Guide lists the largest input each running time handles at its conservative estimate of steps a second. Python does about a tenth as many steps, so its limits are lower: a tenth of the pairs means an about 3 times smaller, and a tenth of the triples an about 2 times smaller.
| Candidates | How many | Largest , C++ | Largest , Python |
|---|---|---|---|
| every pair | about 7,500 | about 2,400 | |
| every triple | about 400 | about 190 |
USACO Guide, Time Complexity(opens in a new tab) ↗
So when is at most a few hundred, a triple loop fits, and when reaches 100,000, even a pair loop is far too slow: the problem setter expects a faster method, and the DSA lessons teach those. The figures are rough, so use them to decide before you write the code, and time the program if the estimate lands near the limit.
Choosing what to enumerate
In Making Triangle each candidate is a choice of positions in a list. In some problems the candidates are something else, and deciding what they are is the first step of a brute force.
You have coins of 500 yen, coins of 100 yen and coins of 50 yen. In how many ways can you pick some of them so that they add up to exactly yen? Coins of the same kind are identical: two ways differ only when they use a different number of some kind of coin.
Constraints
- , and is a multiple of 50
Sample 1 · Input
2 2 2 100
Output
2
Sample 2 · Input
5 1 0 150
Output
0
Sample 3 · Input
30 40 50 6000
Output
213
In the first sample you have two coins of each kind and want 100 yen: one 100-yen coin or two 50-yen coins, two ways. In the second, no mix of 500s and a single 100 makes 150, so the answer is 0.
Coins of one kind are identical, so it does not matter which 100-yen coin you take, only how many. A way to pay is therefore three numbers: how many 500s, how many 100s and how many 50s. Those three counts are the candidates.
Each count runs from 0 up to the number of coins of that kind, so three nested loops list every combination exactly once. With 50 coins of each kind, each count has 51 possible values, 0 to 50:
That is a fraction of a second in either language.
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ways = 0
for n500 in range(a + 1):
for n100 in range(b + 1):
for n50 in range(c + 1):
if 500 * n500 + 100 * n100 + 50 * n50 == x:
ways += 1
print(ways)Each loop includes its upper limit: range(a + 1) goes up to a. With range(a) the program would never try using every coin of a kind, and the first sample, which needs both 50-yen coins, would print 1 instead of 2.
Fixing some choices and computing the rest
Sometimes, once some of the choices are fixed, only one value is left for the rest, and then only the free choices need a loop. A small problem shows the idea:
Cakes cost 4 dollars and doughnuts cost 7 dollars. Can you buy some of them, zero of either allowed, for exactly dollars? Print Yes or No.
Constraints
Sample 1 · Input
11
Output
Yes
Sample 2 · Input
40
Output
Yes
Sample 3 · Input
3
Output
No
Eleven dollars buys one cake and one doughnut, . Forty buys ten cakes. No combination costs exactly three dollars.
Two loops, over cakes and over doughnuts, would work as they did for coins. But once the number of cakes is fixed, the rest of the money must all go on doughnuts, and that works only if the money left is a multiple of 7. So one loop over the number of cakes, from 0 up to , checks the remainder each time.
n = int(input())
answer = "No"
for cakes in range(n // 4 + 1):
if (n - 4 * cakes) % 7 == 0:
answer = "Yes"
print(answer)For , two loops would try combinations and one loop tries 26. Both are instant here.
The saving matters once the limits are larger, and Coins has the same shortcut. Fix the numbers of 500s and 100s, and the rest of the money must be paid in 50s, so the number of 50s is what is left of divided by 50. That works when it is a whole number from 0 to . If each kind went up to 10,000 coins instead of 50:
At steps a second, three loops take more than a day and two loops about 10 seconds.
Stopping at the first answer
Sometimes you need one answer, not all of them. Say we want to print one pair from the opening list that adds up to 9. The pair loop finds 3 + 6 first, and nothing after that matters. break ends a loop at once, so it seems enough to put a break after the print:
nums = [3, 8, 1, 6]
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == 9:
print(nums[i], nums[j])
breakIt prints two pairs. A break ends only the loop it is written in, here the inner loop over j. The outer loop then moves on to i = 1, and the inner loop finds 8 + 1.
Leaving every loop with return
To stop all the loops at once, put them in a function and return from it. A return ends the whole function call, however many loops it is inside.
def print_pair(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
print(nums[i], nums[j])
return
print("No pair")
print_pair([3, 8, 1, 6], 9)
print_pair([3, 8, 1, 6], 100)The first call prints 3 6 and stops. In the second, no pair adds up to 100, so both loops run to the end and the line after them prints No pair.
Using brute force to check a faster solution
When a brute force is fast enough, it is usually the best solution to submit: it is short, and it is correct as long as it lists every candidate. When it is too slow, it is still worth writing, because its answers can check a faster idea.
Take the number of pairs whose sum is even, for up to 100,000 numbers. The pair loop would need checks, far too many. A faster idea uses parity: a sum of two numbers is even when both are even or both are odd. If numbers are even and are odd, the pairs you want are the pairs among the evens plus the pairs among the odds, and the pair formula counts each:
That takes one pass over the numbers, but it is easy to get a formula like this slightly wrong. To check it, the program below runs the brute force and the formula on 1,000 small random lists and counts the lists where they disagree. Testing a fast solution against a slow, simple one on many random inputs is called a stress test.
def brute(a):
count = 0
for i in range(len(a)):
for j in range(i + 1, len(a)):
if (a[i] + a[j]) % 2 == 0:
count += 1
return count
def fast(a):
even = 0
for x in a:
if x % 2 == 0:
even += 1
odd = len(a) - even
return even * (even - 1) // 2 + odd * (odd - 1) // 2
random.seed(1)
wrong = 0
for test in range(1000):
a = []
for _ in range(random.randint(0, 8)):
a.append(random.randint(1, 20))
if brute(a) != fast(a):
wrong += 1
print("different on", a)
print(wrong, "of 1000 tests differ")Python details
random.randint(lo, hi) gives a random whole number from lo to hi, both included. random.seed(1) makes the program pick the same random numbers on every run, so a failing test can be run again.
The lists hold at most 8 numbers, so a failing list is small enough to check by hand, and the program prints it. Suppose the formula had left out the division by 2. Then the list [2, 4] would show the bug at once: the brute force finds one pair and the formula says 2.
Deeper read: counting subsets and orders
The 6 in the triple count is the number of orders three positions can come in, and fixing keeps exactly one of them.
Two other kinds of candidate come up often, and they grow much faster than pairs or triples. A subset of elements is any selection of them, from none to all. Each element is either in or out, so there are subsets. Putting elements in every possible order gives orders.
That is why USACO Guide puts the largest input for every subset at about 20 and for every order at about 10.
Nested loops cannot list these, because the number of loops would have to change with . Recursion with one call per choice handles it, since a subset is an in-or-out choice for each element, and the DSA roadmap's Complete search topic lists every subset with the bits of a number.
Common mistakes
Starting the inner loop at 0 instead of
i + 1.- Where it breaks
- Counting pairs that add up to 6 in
[3, 6, 3]prints 4 instead of 1: the pair of 3s is counted in both orders, and each 3 is also paired with itself. - The fix
- Start
jati + 1, andkatj + 1, so each group of positions appears once.
Using
breakin the inner loop to stop the whole search.- Where it breaks
- Printing one pair that adds up to 9 in
[3, 8, 1, 6]prints3 6and then8 1: thebreakends the loop overj, and the loop overicarries on. - The fix
- Put the loops in a function and
returnas soon as the answer is found.
Checking only one of the three triangle inequalities.
- Where it breaks
- In Making Triangle with sticks
1 2 10, the single checkb + c > apasses, since 12 is more than 1, and the program prints 1. The answer is 0, because 1 + 2 is less than 10. - The fix
- Check all three:
a + b > c,a + c > bandb + c > a. Equivalently, sort the three lengths and check that the two shorter ones add up to more than the longest.
Recall A brute force checks every triple $i < j < k$ of 5,000 numbers. Will it finish in 2 seconds?
No. There are triples, about 2,000 seconds at steps a second, which is over half an hour.
Recall In Coins, why are the candidates the numbers of each kind of coin, rather than groups of coins?
Coins of one kind are identical, so two groups that use the same number of each kind are the same way to pay. Listing groups of coins would count such a way several times; listing the three counts lists each way once.
Key terms
| Term | Meaning |
|---|---|
| candidate | One possible answer the program can check: a pair of positions, a triple, a combination of counts. |
| brute force | Trying every candidate and checking each one; also called complete search. |
| nested loop | A loop inside another loop: the inner loop runs all the way through for each pass of the outer one. |
| stress test | Running a fast solution and a simple brute force on many small random inputs and comparing their answers. |
| subset | Any selection of a list's elements, from none to all: of them for elements. |
