Making Change With combinations()

00:00 In this lesson, you’ll solve a classic interview puzzle by brute force, letting itertools generate every possible choice for you. Here’s the puzzle.

00:10 Your wallet holds three $20 bills, five tens, two fives, and five ones. How many different ways can you make change for a $100 bill? To brute-force it, you’d list every way to pick one bill, then every way to pick two bills, and so on, and check which picks add up to 100.

00:30 A choice of k things from a collection of n things is called a combination. Take three bills, a 20, a 10, and a 5, and choose two of them. You can pick the 20 and the 10, the 20 and the 5, or the 10 and the 5.

00:45 Order doesn’t matter here, so 10 and 20 is the same pick as 20 and 10. That gives you three combinations, and itertools can list them for you.

00:55 Here’s combinations() in the REPL. Pass it an iterable and a size, and it yields every combination as a tuple, the same three you just saw. Now put every bill from the wallet in a list.

01:07 Start with an empty list for the solutions. Then, loop over every possible number of bills from 1 to 15, and keep each combination that adds up to 100.

01:21 You find 44 of them. But that number is suspiciously high. combinations() treats every bill as a separate item, so three 20s and four 10s shows up once for each set of four 10s you could pick.

01:37 Converting the list to a set removes those repeats. Loop over the sorted sets and print each way. There are exactly five ways to make change from your wallet.

01:47 The first three ways use three 20s, and the last two use only two. Now change the puzzle. How many ways can you make change for a $100 if you have any number of 50s, 20s, 10s, 5s, and 1s?

02:01 You need combinations that can repeat a bill. Choosing two from 1 and 2 with combinations() gives you a single pair. combinations_with_replacement() lets each element repeat, so you also get 1 and 1 and 2 and 2.

02:18 The solution looks almost the same as before. This time the list holds one of each kind of bill. Start again with an empty list. You might need up to 100 bills, so the loop goes up to 100, and it uses combinations_with_replacement() instead.

02:38 There are 343 ways, and no duplicates to remove. If you run this yourself, you’ll notice that it takes a while. It checks more than 96 million combinations.

02:51 In this lesson, you brute-forced two versions of the change-making puzzle with combinations() and combinations_with_replacement().

02:59 That last search hinted at a real danger. The number of possibilities grows very fast. Next up, you’ll meet two more brute-force tools, permutations() and product(), and see just how fast that growth can be.