Combination Sum IV
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
Given an array nums of distinct positive integers and a positive integer target, return the number of ordered sequences of numbers from nums that add up to exactly target. Each number may be used any number of times.
Despite the name, order matters: (1,2) and (2,1) are different sequences and both count. That makes this a counting question about *compositions*, the same shape as climbing stairs where each step size comes from nums.
The tests keep the answer below 2^31, as LeetCode promises.
Examples
Input: nums = [1,2,3], target = 4 Output: 7
The seven sequences are (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2) and (3,1).
Input: nums = [9], target = 3 Output: 0
No sequence of 9s adds up to 3.
Constraints
- 1 <= len(nums) <= 200
- 1 <= nums[i] <= 1000
- All the numbers in nums are distinct
- 1 <= target <= 1000
- the answer is less than 2^31
Approaches
- Memoized recursion on the remaining total — time O(target · n), space O(target)
Follow-up
If negative numbers were allowed in nums, how would the problem change, and what restriction would be needed to keep the count finite?
Related problems
Start free on Cariara · Coding problems · System design studio
