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

More DP 1D practice problems

See all DP 1D problems →