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. Your wallet holds three twenty-dollar bills, five tens, two fives, and five ones.

00:16 How many different ways can you make change for a hundred-dollar 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 a hundred.

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

00:45 Order doesn’t matter here, so ten and twenty is the same pick as twenty and ten. 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:09 Start with an empty list for the solutions. Then loop over every possible number of bills, from one to fifteen, and keep each combination that adds up to a hundred.

01:23 You find forty-four of them. But that number is suspiciously high. combinations() treats every bill as a separate item, so three twenties and four tens shows up once for each set of four tens you could pick.

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

01:48 The first three ways use three twenties, and the last two use only two. Now change the puzzle. How many ways can you make change for a hundred if you have any number of fifties, twenties, tens, fives, and ones?

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

02:19 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 a hundred bills, so the loop goes up to a hundred, and it uses combinations_with_replacement() instead.

02:40 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 ninety-six million combinations!

02:51 In this lesson, you brute-forced two versions of the change-making puzzle with combinations() and combinations_with_replacement(). That last search hinted at a real danger: the number of possibilities grows very fast.

03:04 Next up, you’ll meet two more brute-force tools, permutations() and product(), and see just how fast that growth can be.