Combination Sum IV
You're given an array of distinct positive integers nums and a target integer. Return how many ordered sequences of values from nums add up to target. Each value can be used any number of times, and sequences that use the same values in a different order count separately. The answer fits in a 32-bit integer.
Examples
nums = [1,3], target = 5 returns 4
The sequences are (1,1,1,1,1), (1,1,3), (1,3,1), and (3,1,1). The three orders of 1, 1, and 3 each count.
nums = [2,3], target = 7 returns 3
Only one multiset works, two 2s and a 3, and it can be ordered as (2,2,3), (2,3,2), or (3,2,2).
nums = [2,5], target = 3 returns 0
No mix of 2s and 5s adds up to 3.
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All values in nums are distinct.
- 1 <= target <= 1000
Hints
Think about the last number in a sequence that reaches the target. What is left before it?
Use 1-D dynamic programming over the running total: the count for t comes from the counts for t minus each value.
Set dp[0] = 1. For t from 1 to target, add dp[t - x] to dp[t] for every x in nums with x <= t. Return dp[target].
Drill This: Your Approach First
Approach
Let dp[t] be the number of ordered sequences that sum to t, with dp[0] = 1 for the empty sequence. Every sequence summing to t ends in some value x from nums, and what comes before it is a sequence summing to t - x. So dp[t] is the sum of dp[t - x] over every x <= t. Fill dp from 1 up to target with the totals in the outer loop and the values in the inner loop. O(target * n) time, O(target) space.
Time
O(target * n)
Space
O(target)
Pitfall
Solutions
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int t = 1; t <= target; t++) {
for (int x : nums) {
if (x <= t) dp[t] += dp[t - x];
}
}
return dp[target];
}
}class Solution:
def combinationSum4(self, nums, target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for t in range(1, target + 1):
for x in nums:
if x <= t:
dp[t] += dp[t - x]
return dp[target]