Free Dynamic programming lessonsDynamic programming · Stage 5 · Knapsack · Step 4

Counting combinations, not arrangements

Coins on the outside, amount on the inside — the loop order that stops order from mattering. About 13 minutes.

Combinations, not orders

How many ways can you pay 5 rupees with 1, 2 and 5 rupee coins? Paying 1 + 2 + 2 or 2 + 1 + 2 is the same handful of coins, so it should only count once. You want combinations, not orders.

Getting that right is all about the order you do things in.

1 + 2 and 2 + 1: are the same coins: count them once.

Finish one coin before starting the next

Bring the coins in one kind at a time. First count every amount using only 1s. Then add in the 2s, then the 5s. Because each kind of coin is added after the ones before it are completely done, a handful is always built in the same coin order, so it's only ever counted once.

When a coin is added, every way to make the amount minus that coin becomes a way to make the amount. For 5 rupees you get 4 ways: five 1s, three 1s and a 2, one 1 and two 2s, or a single 5.

Coins on the outside: each handful is counted exactly once.

Amounts on the outside: would count every order separately.

In code

for a in range(1, 4):
    for coin in (1, 2):
        # amount outside: orders count
        pass

coins = [1, 3, 4], amount = 7 · one coin at a time

01234567

start

coin 1

coin 3

coin 4

There's exactly one way to make 0: use no coins. Now bring the coins in one kind at a time, fully.

Move 1 of 5

Quick check

Coins are 1 and 2. Using only 1s, there's exactly 1 way to make each amount. After adding the 2s, how many ways make 3?

Show the answer

2. The old way (1 + 1 + 1) plus the new one using a 2 (1 + 2).

Your problem

Ways to make an amount

You get coins, a list of coin values, and a target amount. You have an unlimited supply of each coin. Return how many different combinations of coins add up to exactly amount — combinations, so using the same coins in a different order doesn't count again.

Example

coins = [1, 2, 5], amount = 5 → 4

0 ≤ coins.length ≤ 100 · 1 ≤ coins[i] ≤ 1,000 · 0 ≤ amount ≤ 1,000 · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.