Count Ordered Sequences That Sum to a Target
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Ordered Sequences That Sum to a Target
Count the distinct ordered sequences whose elements sum exactly to a positive target. You may use each allowed value repeatedly. Two sequences containing the same values in a different order count separately. Return a nonnegative integer count; return zero if no sequence reaches the target.
### Part 1 — Existing order-size variant
Implement `count_order_sequences(n, sizes) -> int`.
#### Constraints
- `1 <= n <= 10000`.
- `1 <= len(sizes) <= 100`.
- Every size is unique and lies between `1` and `n`.
- The answer is at most `2^53 - 1`.
```text
n = 3, sizes = [1, 2]
result = 3
```
The sequences are `[1,1,1]`, `[1,2]`, and `[2,1]`.
```text
n = 3, sizes = [2]
result = 0
```
#### What This Part Should Cover
- Counting each ordered sequence once, including repeated uses of an allowed size.
- Unreachable targets and the distinction between sequence order and an unordered selection.
- Exact numeric results throughout the stated target and answer ranges.
### Part 2 — Source API variant
Implement `Solution.combinationSum4(nums, target) -> int` with the same ordered counting rule and these separate constraints:
- `1 <= len(nums) <= 200`.
- All values are distinct integers from `1` through `1000`.
- `1 <= target <= 1000`.
- The nonnegative answer fits a signed 32-bit integer.
Values greater than `target` are legal in this variant. Keep them valid input even when they cannot participate in a successful sequence. The existing coding view retains the Part 1 function and constraints; the written source API does not change that console.
```text
nums = [1, 2, 3], target = 4
result = 7
```
The sequences are `[1,1,1,1]`, `[1,1,2]`, `[1,2,1]`, `[2,1,1]`, `[2,2]`, `[1,3]`, and `[3,1]`.
```text
nums = [9], target = 3
result = 0
```
#### What This Part Should Cover
- The source method signature, its larger allowed-value count, and legal values greater than the target.
- The separate final-answer guarantee, without assuming it automatically bounds every intermediate quantity.
- Correctness and time and space costs for this input range.
### What a Strong Answer Covers
The solution implements both interfaces without merging their different input bounds or answer guarantees. It explains why order is counted correctly, why positive values make the unrestricted-length task well defined, and how the arithmetic preserves exact results.
### Follow-up Questions
- What changes if negative numbers are allowed among the values? Discuss when the count is finite or infinite, and propose an additional restriction that makes the modified counting task well defined. Explain how your solution would change under that restriction.
```hint Distinguish order explicitly
For allowed values `[1,2]`, `[1,2]` and `[2,1]` are different sequences.
```
```hint Check unreachable totals
Include a target that cannot be formed because the allowed values share an incompatible common divisor.
```
Overview: Given a positive target n and a set of unique positive order sizes, count the distinct ordered sequences of any length whose elements sum exactly to n. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given a positive target `n` and unique positive allowed sizes, count all finite ordered sequences whose elements sum exactly to `n`. A size may be reused, and two sequences with the same elements in a different order are distinct.
Constraints
- 1 <= n <= 10000; 1 <= len(sizes) <= 100.
- Every size is unique and lies from 1 through n; sizes may be reused in a sequence.
- Sequence order matters and the exact answer is at most 2^53 - 1.
Examples
Input: (1, [1])
Expected Output: 1
Explanation: The only sequence is one occurrence of size one.
Input: (3, [1, 2])
Expected Output: 3
Explanation: The valid ordered sequences are 1+1+1, 1+2, and 2+1.
Hints
- For sizes 1 and 2, compare the two different orders that reach target 3.
- Test one size equal to the target and a target unreachable from all allowed sizes.
- Include the maximum target with many large allowed sizes and a wide but exact result case.
Community answers
Answer by el_bald
#include
using namespace std;
typedef long long ll;
class Solution {
public:
long long count_order_sequences(int n, const std::vector& sizes) {
vector dp(n + 1); dp[0] = 1;
int m = sizes.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if (i + sizes[j] <= n) {
dp[i + sizes[j]] += dp[i];
}
}
}
return dp[n];
}
};