Skip to main content

377. Combination Sum IV

medium

Count 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 Sam K., 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 <= 200
  • 1 <= nums[i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

Examples

Example 1

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

Explanation: 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

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

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

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Recursion practice problems

See all Recursion problems →