Count Ways to Reach Step n With a Given Set of Step Sizes

You are climbing a staircase with n steps, starting on the ground (step 0). Every move offers the same set of choices: you pick one of the allowed step sizes in steps and climb exactly that many steps. Return the number of distinct move sequences that end exactly on step n.

In the interview, a follow-up asked whether the extra space used by the solution could be reduced.

Function Signature

def count_ways(n: int, steps: list[int]) -> int:

Rules

• Order matters: two sequences are different if they have different lengths or choose a different step size at some position, so 1 + 2 and 2 + 1 are different sequences.
• The step sizes in a sequence must add up to exactly n.
• Each allowed step size can be used any number of times, and steps may be given in any order.
• If no sequence reaches step n exactly, return 0.

Constraints

• 1 <= n <= 50
• 1 <= len(steps) <= 50
• The values in steps are distinct, and 1 <= steps[i] <= 50.
• The answer is at most 2^49 (reached when n = 50 and every size from 1 to 50 is allowed). That exceeds the 32-bit signed range but stays below 2^53, so use 64-bit integers.

Examples

Example 1

Input:  n = 4, steps = [1, 2]
Output: 5

The sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.

Example 2

Input:  n = 5, steps = [1, 3, 5]
Output: 5

The sequences are 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1 and 5.

Example 3

Input:  n = 7, steps = [2, 4]
Output: 0

Every allowed size is even, so no sequence adds up to 7.

Count Ordered Ways to Climb Stairs with Custom Step Sizes

Hints

1. Order matters: 1 + 2 and 2 + 1 are different sequences, so make sure your counting does not merge sequences that use the same sizes in a different order.
2. Sizes may be listed in any order, and a size larger than n can never be used; neither fact should break your solution.
3. Counts can reach 2^49, beyond the 32-bit signed range, so accumulate them in a 64-bit integer type.

Approach

Let ways[i] be the number of ordered move sequences that end exactly on step i, with ways[0] = 1 for the empty sequence. Every sequence ending on step i >= 1 has a well-defined last move s, which must be an allowed size with s <= i, and removing it leaves a sequence ending exactly on step i - s. Conversely, appending s to any sequence ending on i - s yields a distinct sequence ending on i. Grouping sequences by their last move therefore partitions them, so ways[i] = sum of ways[i - s] over allowed sizes s <= i. Because the last move is part of what distinguishes sequences, 1+2 and 2+1 are counted separately; looping over sizes in the outer loop instead would count unordered combinations and is wrong here. Filling ways[1..n] in increasing order guarantees every referenced entry is already final. Sizes larger than i are skipped one by one rather than ending the loop, so unsorted input and sizes greater than n are handled; if nothing reaches n, ways[n] stays 0. Each ways[i] is at most the number of compositions of i, 2^(i-1) <= 2^49, so 64-bit integers (and JavaScript numbers, exact below 2^53) never overflow. Follow-up on space: ways[i] depends only on the previous max(steps) entries, so a circular buffer of size min(n, max(steps)) + 1 reduces the extra space to O(min(n, max(steps))) with the same running time.

• Time complexity: O(n * k), where k = len(steps)
• Space complexity: O(n)