hardDynamic Programming 1DAI-applied~30 min
Count Ordered Ways to Reach a Target Budget
A generator appends one chunk at a time, each chunk drawn from a set of allowed sizes, until the total length hits a target. Count the number of distinct ordered build sequences that reach the target exactly.
Problem
Given an array of distinct positive integers nums and a target integer, return the number of possible combinations (ordered sequences) that sum to target. Different orderings count as different combinations.
Input
An array nums of distinct positive integers and an integer target.
Output
An integer: the number of ordered sequences summing to target.
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000, all distinct
- 1 <= target <= 1000; the answer fits in a 32-bit integer.
Examples
Example 1
Input
nums = [1,2,3], target = 4
Output
7
Ordered sequences: (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2),(1,3),(3,1).
Example 2
Input
nums = [9], target = 3
Output
0
No sequence of 9s sums to 3.