Lesson 3 of 16

Try Every Candidate

You want two product prices to add up exactly to a budget. One starting method is to check every possible pair. This is exhaustive search, or brute force.

A useful starting point for small inputs

Brute force generates every candidate and checks the requirements. For optimization, it must select the best among all valid candidates. Its simplicity also makes it useful as a reference for comparing a faster solution.

def find_pair(prices, budget):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] + prices[j] == budget:
                return (i, j)
    return None

print(find_pair([2, 5, 9, 7], 9))

This prints (0, 3): prices 2 and 7 total 9. Starting j at i + 1 avoids selecting the same product twice. If several answers exist, the function returns the first pair found by these loops.

Count candidates first

• Choosing two items creates roughly n²/2 candidates.
• Independently including or excluding each item creates 2^n subsets.
• Ordering all distinct items creates n! permutations.

Also account for checking each candidate. With 2^n candidates and n work per check, total time is O(n·2^n). Candidate count alone need not be the full running time.

A clue toward a faster method

After seeing price x, the required partner is budget - x. Remembering previous prices in a hash table avoids repeatedly scanning all earlier products. Choose the lookup and insertion order carefully so one product is not reused. See the hashing lesson.

Check your understanding

Can [4, 4] form a total of 8? Why should [4] give a different result?