Show problems as
Classic problem #377MediumArrayDynamic Programming

Combination Sum IV

Real-world version: Slab Layouts Along A Path
Tracked in this browser only
Read Combination Sum IV on LeetCode(opens in a new tab)

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

A yard sells paving slabs in the widths listed in widths, all different, and holds an unlimited number of each. A path of length span is laid by putting slabs down one after another from the gate outwards, and it counts as finished when the widths laid add up to exactly span.

Two layouts are the same only when they lay the same widths in the same order from the gate. So on a span of 5 with widths 2 and 3 available, laying 2 then 3 is one layout and laying 3 then 2 is a second.

Return how many layouts finish the path. Return 0 if none do. The count is guaranteed to fit in a signed 32-bit integer for every input you are given.

Examples

Example 1

Input
widths = [5, 7, 11], span = 22
Output
5

Two slabs of 11 finish the path, and so does a run of three 5s together with one 7, which can be laid in four orders depending on where the 7 goes.

Example 2

Input
widths = [4, 6], span = 9
Output
0

No run of 4s and 6s adds up to 9.

Example 3

Input
widths = [8], span = 24
Output
1

Three 8s reach 24, and that is the only layout available.

Constraints

  • 1 <= widths.length <= 200
  • 1 <= widths[i] <= 1000
  • All the widths are distinct.
  • 1 <= span <= 1000
  • 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 slab_layouts(widths: list[int], span: int) -> int:
Java
public int slabLayouts(int[] widths, int span)

More on the same topics