314. Combination Sum IV
You are given an array nums of distinct positive integers and a positive integer target.
Count how many different sequences of elements from nums add up to exactly target. Each element may be reused any number of times, and order matters: (1, 2) and (2, 1) count as two different sequences. Despite the title, you are really counting permutations, not combinations.
Return that count as a single integer. The test data guarantees the answer fits in a signed 32-bit integer.
Follow-up to think about: what would change if nums could contain negative numbers?
Example 1:
Input: nums = [1, 2, 3], target = 4
Output: 7
Explanation: The 7 sequences are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1). Note that reorderings such as (1,3) and (3,1) are counted separately.
Example 2:
Input: nums = [9], target = 3
Output: 0
Explanation: The only available element is 9, which already overshoots 3, so no sequence works.
Constraints:
- 1 ≤ nums.length ≤ 200
- 1 ≤ nums[i] ≤ 1000
- All elements of nums are distinct.
- 1 ≤ target ≤ 1000
- The answer is guaranteed to be less than 2³¹.
Hints:
Order matters, so do not enumerate multisets. Think about the first element instead: every valid sequence starts with some nums[i], and what follows is a valid sequence for target - nums[i]. That is a recursion on the remaining amount alone.
The recurrence count(t) = Σ count(t − x) over all x in nums with x <= t, with count(0) = 1, has only target + 1 distinct inputs. Memoize the recursion, or fill a dp array from 0 up to target.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3], target = 4
Expected output: 7