0160MediumArrayDynamic ProgrammingKnapsack ProblemComplete Knapsack

Ribbon Spool Assemblies

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def spool_assemblies(target: int, spools: list[int]) -> int:

Java

public int spoolAssemblies(int target, int[] spools)

The intended approach

Time O(len(spools) * target)Space O(target)

Let `ways[t]` be the number of assemblies reaching exactly `t` centimetres while drawing only from the spool lengths considered so far. Introducing one more length and sweeping `t` upward lets that length be reused any number of times, because `ways[t - length]` has already absorbed the new length by the time it is read. Keeping the length on the outer loop is what makes each assembly counted once instead of once per ordering of its spools.

Pythonentry point: spool_assemblies

def spool_assemblies(target, spools):
    # Time O(len(spools) * target): one sweep of the table per spool length.
    # Space O(target): a single row of counts, reused across lengths.
    ways = [0] * (target + 1)
    ways[0] = 1
    for length in spools:
        for total in range(length, target + 1):
            ways[total] += ways[total - length]
    return ways[target]

The obvious version

Walk the spool lengths one at a time and try every possible number of spools at the current length before recursing on the rest, with no table and no memoisation. Every assembly is generated exactly once because the lengths are fixed in a single order.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_spool_assemblies(target, spools):
    lengths = list(spools)

    def walk(index, left):
        if left == 0:
            return 1
        if index == len(lengths):
            return 0
        found = 0
        used = 0
        while used <= left:
            found += walk(index + 1, left - used)
            used += lengths[index]
        return found

    return walk(0, target)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in