loading

377. Combination Sum IV — Step-by-Step Visualization

mediumLeetCode #377ArrayDynamic Programming

Given an array of **distinct** integers `nums` and a target integer `target`, return the number of possible combinations that add up to `target`. The order of numbers in the combination **matters** (so permutations count separately). **Example:** Input: `nums = [1,2,3]`, `target = 4` Output: `7` Explanation: `(1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1)`

Algorithm Pattern

Unbounded Knapsack (ordered)

Key Idea

dp[i] = number of ordered ways to reach sum i. Because order matters, the outer loop is over targets (not nums), so each arrangement is counted separately.

Step-by-Step Approach

  1. Initialize dp[0] = 1 (one way to reach 0: pick nothing), dp[1..target] = 0.
  2. For i from 1 to target:
  3. For each num in nums:
  4. If i >= num: dp[i] += dp[i - num].
  5. Return dp[target].

Common Gotchas

  • Outer loop = target, inner loop = nums → counts permutations (order matters).
  • Swap the loops (outer = nums) and you get combination count (order ignored) — like Coin Change II.

Related Problems

← All problems