Count how many ordered sequences can sum to a target using the given numbers any number of times.
Given an array of distinct positive integers nums and a positive integer target, count how many different ordered sequences can be formed using elements from nums so that their sum is exactly target.
You may use each number in nums any number of times. Two sequences are considered different if they differ in at least one position, even if they contain the same values in a different order.
Return the total number of valid sequences.
Input Format
- An integer array
numsof distinct positive integers. - An integer
target.
In an interview setting, these are typically provided directly as function arguments.
Output Format
- Return a single integer: the number of ordered sequences whose sum equals
target.
Constraints
1 <= nums.length1 <= nums[i]numscontains distinct values.1 <= target- The count may exceed 32-bit integer range in some languages; use an appropriate integer type if needed.
Example 1
Input
nums = [1,2,3], target = 4
Output
7
Explanation
The valid ordered sequences are:
- [1,1,1,1]
- [1,1,2]
- [1,2,1]
- [2,1,1]
- [2,2]
- [1,3]
- [3,1]
There are 7 in total.
Example 2
Input
nums = [9], target = 3
Output
0
Explanation
No sequence made from 9 can sum to 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.