Show problems as
Classic problem #518MediumArrayDynamic ProgrammingKnapsack ProblemComplete Knapsack

Coin Change II

Real-world version: Ribbon Spool Assemblies
Tracked in this browser only
Read Coin Change II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstKnapsack Problems · Dynamic Programming, animated step by step

A bindery keeps ribbon wound on spools of a few fixed lengths, given in spools. The lengths listed are all different from one another, and the storeroom carries an unlimited number of spools at each of those lengths.

An order calls for exactly target centimetres of ribbon, put together by joining whole spools end to end. A spool is never cut. Count how many different assemblies hit the order exactly.

Two assemblies count as the same whenever they draw the same number of spools at every length, so the sequence in which the spools get joined is irrelevant.

A target of 0 is a legal order, and the assembly that joins nothing at all fills it, so the answer in that case is 1. When no assembly reaches target, answer 0. The count is guaranteed to fit in a signed 32-bit integer.

Examples

Example 1

Input
target = 6, spools = [1, 3, 4]
Output
4

The four assemblies are one 4 beside two 1s, two 3s, one 3 beside three 1s, and six 1s.

Example 2

Input
target = 7, spools = [5]
Output
0

Joining spools of length 5 can only ever reach a multiple of 5, and 7 is not one.

Example 3

Input
target = 0, spools = [2, 7]
Output
1

Nothing has to be joined to fill an order of zero centimetres, and that empty assembly is the single way to do it.

Constraints

  • 1 <= spools.length <= 300
  • 1 <= spools[i] <= 5000
  • All lengths in spools are distinct.
  • 0 <= target <= 5000
  • The answer fits in a signed 32-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def spool_assemblies(target: int, spools: list[int]) -> int:
Java
public int spoolAssemblies(int target, int[] spools)

More on the same topics