Combination Sum IV
MediumDynamic Programming
You are given a list of distinct positive integers nums and a positive integer target.
Return the number of ordered sequences of values from nums that add up to target. Each value may be used any number of times, and sequences with the same values in a different order are counted separately (so 1, 2 and 2, 1 are two different sequences). If no sequence works, return 0.
Example 1
- Input:
- nums = [1, 2], target = 4
- Output:
- 5
- Explanation
- The sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
- Input:
- nums = [2, 4, 6], target = 8
- Output:
- 7
- Explanation
- 2+2+2+2 and 4+4 count once each, 2+2+4 counts three times (the 4 can be in any of three positions) and 2+6 counts twice, for 1 + 1 + 3 + 2 = 7.
Example 3
- Input:
- nums = [4, 5], target = 3
- Output:
- 0
- Explanation
- Every value is larger than 3, so nothing can sum to it.
Constraints
- 1 ≤
nums.length≤ 200 - 1 ≤
nums[i]≤ 1000 - All values in
numsare distinct - 1 ≤
target≤ 1000 - The answer fits in a signed 32-bit integer