Count Ways to Reach Step n With a Given Set of Step Sizes
Company: Squarepoint
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: n = 7, steps = [2, 4]
Output: 0
```
Every allowed size is even, so no sequence adds up to 7.
Overview: From a Squarepoint technical screen: count the ordered sequences of moves that climb exactly n stairs when every move uses a step size from a given set. It tests careful counting of ordered choices, targets that cannot be reached, and the interviewer's follow-up about reducing the extra space the solution uses.
Read the full Squarepoint Data Scientist interview experience this question came from
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`.
**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`.
**Follow-up:** can you reduce the extra space your solution uses?
**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). It can exceed `2^31 - 1` but stays below `2^53`, so use 64-bit integers (`long` in Java, `long long` in C++).
**Example 1**
```text
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**
```text
Input: n = 7, steps = [2, 4]
Output: 0
```
Every allowed size is even, so no sequence adds up to 7.
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 (n = 50 with every size from 1 to 50 allowed); it can exceed 2^31 - 1 but stays below 2^53, so use 64-bit integers (Java long, C++ long long)
Examples
Input: (4, [1, 2])
Expected Output: 5
Explanation: Example 1: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Input: (7, [2, 4])
Expected Output: 0
Explanation: Example 3 of the source: every allowed size is even, so the odd target 7 is unreachable.
Hints
- 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.
- Sizes may be listed in any order, and a size larger than n can never be used; neither fact should break your solution.
- Counts can reach 2^49, beyond the 32-bit signed range, so accumulate them in a 64-bit integer type.