Room 04 · The Grind — 1-D Dynamic Programming

Combination Sum IV

MEDIUM✓ CHIP-TIMEDLC #377 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Count the distinct ORDERED sequences of numbers from a set (reuse allowed, order matters) that add up to a target — [1,2] and [2,1] count as two separate sequences, not one.

A set of distinct positive numbers and a target arrive together, and the count needed is how many ordered sequences of those numbers add up to exactly the target — numbers can be reused as many times as a sequence needs.

Order matters here despite the name: a sequence like [1,2] and a sequence like [2,1] are counted as two separate sequences, not merged into one combination. Every number in a sequence has to come from the given set, and the sequence's total has to hit the target exactly, no more and no less.

The output is just the count of such sequences, which can get large — there's no need to list the sequences themselves.

the set of numbers contains no duplicates
numbers can be reused any number of times within one sequence
the target stays small enough that the count fits a standard integer
order counts, so [1,2] and [2,1] are two different sequences

EX 01

nums = [1, 2] · target = 4

→ 5

two step sizes, order matters

EX 02

nums = [1, 2, 4] · target = 5

→ 10

EX 03

nums = [7] · target = 4

→ 0

the only step is bigger than the target

The hintstake only what you need

HINT 1 THE NUDGE

Despite the name, this isn't about listing combinations — order matters, so it's really counting sequences. What's the count of sequences that sum to some remaining amount, in terms of smaller remaining amounts?

HINT 2 THE STRUCTURE

ways(t) = the sum, over every number in the set no bigger than t, of ways(t − number). The base case ways(0) = 1 — the empty sequence is the one way to make nothing.

HINT 3 ONE STEP FROM THE ANSWER

Build ways bottom-up from 0 to target instead of recursing fresh each time: a single array where ways[t] is filled once and reused by every larger t that needs it.

Coach's boardthe pattern, step by step

WAYS TO tPATTERN · WAYS-TO-t DPnums = [1, 2] · target = 4

STEP 1

ways[0] = 1 — the empty sequence is the one way to make 0.

STEP 1 / 6 · ← → WORK TOO

The splitstwo paces, two languages

grind/combination-sum-iv.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        ways = [0] * (target + 1)
        ways[0] = 1  # one way to make nothing: pick nothing
        for t in range(1, target + 1):
            for x in nums:
                if x <= t:
                    ways[t] += ways[t - x]
        return ways[target]

TIME O(TARGET·K)SPACE O(TARGET)PYTHON · RACE PACE · 9 LN

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        def ways(remaining: int) -> int:
            if remaining == 0:
                return 1
            if remaining < 0:
                return 0
            total = 0
            for x in nums:
                total += ways(remaining - x)  # x goes first, recompute the rest from scratch
            return total

        return ways(target)

TIME O(K^TARGET)SPACE O(TARGET)PYTHON · TRAINING PACE · 13 LN

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] ways = new int[target + 1];
        ways[0] = 1;
        for (int t = 1; t <= target; t++) {
            for (int x : nums) {
                if (x <= t) {
                    ways[t] += ways[t - x];
                }
            }
        }
        return ways[target];
    }
}

TIME O(TARGET·K)SPACE O(TARGET)JAVA · RACE PACE · 14 LN

class Solution {
    public int combinationSum4(int[] nums, int target) {
        return ways(nums, target);
    }

    private int ways(int[] nums, int remaining) {
        if (remaining == 0) {
            return 1;
        }
        if (remaining < 0) {
            return 0;
        }
        int total = 0;
        for (int x : nums) {
            total += ways(nums, remaining - x);
        }
        return total;
    }
}

TIME O(K^TARGET)SPACE O(TARGET)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED