Loading problem...
You are given an array of distinct positive integers nums and a target integer target. Your task is to determine the total number of distinct ordered sequences that can be formed using elements from nums such that the sum of the sequence equals target.
Each element from the array can be used unlimited times in the sequence, and the order of elements matters—sequences with the same elements in different orders are counted as separate sequences.
The answer is guaranteed to fit within a 32-bit signed integer.
nums = [1,2,3]
target = 47There are 7 distinct ordered sequences that sum to 4: • (1, 1, 1, 1) → 1 + 1 + 1 + 1 = 4 • (1, 1, 2) → 1 + 1 + 2 = 4 • (1, 2, 1) → 1 + 2 + 1 = 4 • (1, 3) → 1 + 3 = 4 • (2, 1, 1) → 2 + 1 + 1 = 4 • (2, 2) → 2 + 2 = 4 • (3, 1) → 3 + 1 = 4 Note that (1, 3) and (3, 1) are counted as distinct sequences because order matters.
nums = [9]
target = 30The only element is 9, which is larger than target 3. There is no way to form a sequence that sums to 3, so the answer is 0.
nums = [1,2,5]
target = 59There are 9 distinct ordered sequences: • (1, 1, 1, 1, 1) • (1, 1, 1, 2) • (1, 1, 2, 1) • (1, 2, 1, 1) • (2, 1, 1, 1) • (1, 2, 2) • (2, 1, 2) • (2, 2, 1) • (5)
Constraints