Combination Sum IV

The key idea

Because order matters, this is a count of ordered sequences, not subsets. Let dp[t] be the number of ordered combinations that sum to t. Any sequence summing to t ends with some num in nums, and the part before it is itself an ordered sequence summing to t - num, so dp[t] is the sum of dp[t - num] over every num <= t.

Problem

Given an array of distinct positive integers nums and a target integer target, return the number of possible combinations that add up to target.

A combination is an ordered sequence of values drawn from nums (a value may be reused any number of times). Two combinations that use the same values in a different order are counted as different combinations. The test cases are generated so that the answer fits in a 32-bit integer.

As a follow-up, consider what changes if negative numbers were allowed in nums: the count could become infinite, so an extra limit on how many times each number may be used would be required.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

Examples

Input: nums = [1,2,3], target = 4 Output: 7

Input: nums = [9], target = 3 Output: 0

Complexity

Time: O(target * n) Space: O(target)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →