377. Combination Sum IV
mediumCount the number of ordered ways to sum to a target using a list of distinct integers, where each integer can be reused. Despite the name, this is really a DP-over-recursion classic where order matters — Climbing Stairs in disguise.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The test cases are generated so that the answer can fit in a 32-bit integer. Note: different orderings count as different combinations.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 1000All the elements of nums are unique.1 <= target <= 1000
Examples
Example 1
nums = [1,2,3], target = 47Explanation: The possible combination ways are: (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3), (2, 1, 1), (2, 2), (3, 1). Note that different sequences are counted as different combinations.
Example 2
nums = [9], target = 30Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Read the note carefully — order matters. (1,2,1) and (1,1,2) are distinct. That's the entire twist.
Hint 2
Recursion: ways(target) = sum over num in nums of ways(target - num) for each num <= target.
Hint 3
Memoize ways(remaining) — there are only target+1 unique states. This collapses exponential into pseudo-polynomial.
Hint 4
Iterative version: dp[t] = sum over nums of dp[t - num]. Build up from dp[0] = 1.
Solution approach
Reveal approach
Because order matters, the recurrence is: ways(t) = sum over num in nums where num <= t of ways(t - num), with ways(0) = 1. The naive recursion is exponential; memoize on remaining target — there are at most target + 1 unique subproblems, so memoized cost is O(target * n). Bottom-up DP: initialize dp[0] = 1, dp[i] = 0 otherwise. For t from 1 to target, for each num in nums, if num <= t add dp[t - num] to dp[t]. Note the outer loop over t and inner loop over nums (not the reverse) — this is what counts ordered sequences. If you swapped the loop order you'd get the Coin Change unordered-count problem instead.
Complexity
- Time
- O(target * n)
- Space
- O(target)
Related patterns
- dynamic-programming
- recursion
- memoization
Related problems
- 39. Combination Sum
- 322. Coin Change
- 70. Climbing Stairs
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
Practice these live with InterviewChamp.AI
Drill Combination Sum IV and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →