MediumNo. 0518

Coin Change II — LeetCode 518 Python Solution

Topics
Array, Dynamic Programming
On a study list
NeetCode 150
Reading time
2 min

The problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount.

Example

Input
amount = 5, coins = [1,2,5]
Output
4
Explanation
there are four ways to make up the amount:

Python solution

PythonSolution
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        m, n = len(coins), amount
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(coins, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i][j - x]
        return f[m][n]

Complexity

Time
O(m × n)
Space · auxiliary
O(m × n)

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 518. Coin Change II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0322Coin ChangeMedium
0526Beautiful ArrangementMedium
0045Jump Game IIMedium
0053Maximum SubarrayMedium
0055Jump GameMedium
0063Unique Paths IIMedium

Frequently asked questions

How hard is LeetCode 518. Coin Change II?

LeetCode 518. Coin Change II is rated Medium on LeetCode.

What is the time complexity of LeetCode 518. Coin Change II?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 518. Coin Change II?

The Python solution on this page uses O(m × n) auxiliary space.

What topics does LeetCode 518. Coin Change II cover?

LeetCode 518. Coin Change II is tagged Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.