Skip to main content

377. Combination Sum IV

medium

Count the number of ordered sequences from nums that sum to target. The permutation cousin of Coin Change II — flip the loop order and the meaning of dp changes.

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 that different sequences are counted 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

Because order matters, the loop order is amounts outside and nums inside — the opposite of Coin Change II.

Hint 2

dp[t] = number of ordered sequences summing to t. Recurrence: dp[t] = sum over num in nums of dp[t - num].

Hint 3

Base case dp[0] = 1. The empty sequence is the one way to reach target 0.

Solution approach

Reveal approach

Define dp[t] as the number of ordered sequences from nums summing to t. dp[0] = 1 — the empty sequence is one way to reach zero. For t from 1 to target: dp[t] = sum over num in nums with num <= t of dp[t - num]. Each addition corresponds to appending num as the LAST element of a sequence — which makes order matter because (1,2) and (2,1) are different last-element choices for target 3. Return dp[target]. O(target * N) time, O(target) space. The exact opposite loop ordering compared to Coin Change II.

Complexity

Time
O(target * N)
Space
O(target)

Related patterns

  • dynamic-programming
  • unbounded-knapsack

Related problems

Asked at

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

  • Amazon
  • Google
  • Facebook

Practice these live with InterviewChamp.AI

Drill Combination Sum IV and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →