title: Combination Sum IV
slug: combination-sum-iv
difficulty: medium
leetcode_id: 377
leetcode_url: https://leetcode.com/problems/combination-sum-iv/
categories:
  - dynamic-programming
  - arrays
patterns:
  - slug: dynamic-programming
    is_optimal: true

function_signature: "def combination_sum4(nums: list[int], target: int) -> int:"

test_cases:
  visible:
    - input: { nums: [1, 2, 3], target: 4 }
      expected: 7
    - input: { nums: [9], target: 3 }
      expected: 0
  hidden:
    - input: { nums: [1], target: 1 }
      expected: 1
    - input: { nums: [1, 2], target: 3 }
      expected: 3
    - input: { nums: [2, 3], target: 6 }
      expected: 4
    - input: { nums: [1, 2, 3], target: 5 }
      expected: 13
    - input: { nums: [3, 4, 5, 6], target: 10 }
      expected: 18
    - input: { nums: [5, 10], target: 15 }
      expected: 3

description: |
  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 sequences are counted as different combinations. For example, `(1, 1, 2)` and `(1, 2, 1)` and `(2, 1, 1)` are all counted separately.

constraints: |
  - `1 <= nums.length <= 200`
  - `1 <= nums[i] <= 1000`
  - All the elements of `nums` are **unique**
  - `1 <= target <= 1000`

examples:
  - input: "nums = [1,2,3], target = 4"
    output: "7"
    explanation: "The 7 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."
  - input: "nums = [9], target = 3"
    output: "0"
    explanation: "No combination of 9s can sum to 3, so return 0."

explanation:
  intuition: |
    Despite its name, this problem is actually counting **permutations**, not combinations — because the order matters! `(1, 2, 1)` and `(1, 1, 2)` are counted as different sequences.

    Think of it like climbing stairs where each step can be any number in `nums`. If you're at stair 0 and want to reach stair 4, how many distinct paths are there? At each position, you can jump by any value in `nums`, and the same jump sequence in different orders counts as different paths.

    The key insight is: to count paths to reach `target`, sum up all paths to positions you could have jumped *from*. If `nums = [1, 2, 3]` and you want to reach 4:
    - You could arrive from position 3 (jump +1)
    - You could arrive from position 2 (jump +2)
    - You could arrive from position 1 (jump +3)

    So: `ways(4) = ways(3) + ways(2) + ways(1)`. This is the **counting DP** pattern applied to permutations.

  approach: |
    We solve this using **Bottom-Up Dynamic Programming**:

    **Step 1: Create and initialise the DP array**

    - Create `dp` of size `target + 1`, where `dp[i]` = number of ways to reach sum `i`
    - Set `dp[0] = 1` as the base case: exactly one way to make sum 0 (use no numbers)
    - All other entries start at 0 (no ways discovered yet)

    &nbsp;

    **Step 2: Build up solutions for each target value**

    - For each sum `i` from 1 to `target`:
      - For each number `num` in `nums`:
        - If `num <= i` (the number doesn't exceed our current target):
          - Add `dp[i - num]` to `dp[i]`
        - This counts: "ways to reach `i` by using `num` as the last element"
      - The total `dp[i]` accumulates ways from all possible last elements

    &nbsp;

    **Step 3: Return the answer**

    - Return `dp[target]` — the total number of sequences summing to target

    &nbsp;

    The order of loops matters! By iterating over sums first (outer) and nums second (inner), we count each ordering separately. This gives us permutations, not combinations.

  common_pitfalls:
    - title: Confusing with Coin Change Combinations
      description: |
        In classic "coin change counting" problems, order doesn't matter: `{1, 1, 2}` and `{1, 2, 1}` are the same combination. For those, you iterate over coins in the outer loop and amounts in the inner loop.

        Here, order matters! The loop order is flipped: amounts outer, numbers inner. This ensures we count `(1, 1, 2)`, `(1, 2, 1)`, and `(2, 1, 1)` as three distinct sequences.

        **Coin change (combinations):** `for coin in coins: for i in range(...)`
        **This problem (permutations):** `for i in range(...): for num in nums`
      wrong_approach: "Using coin-change loop order (coins outer, amounts inner)"
      correct_approach: "Amounts outer, numbers inner to count orderings"

    - title: Wrong Base Case
      description: |
        The base case `dp[0] = 1` is essential. It represents that there's exactly one way to reach sum 0: by choosing nothing.

        If you set `dp[0] = 0`, all subsequent values would be 0 because you'd have no starting point for the recurrence.
      wrong_approach: "dp[0] = 0 or leaving it unset"
      correct_approach: "dp[0] = 1 to bootstrap the recurrence"

    - title: Recursion Without Memoisation
      description: |
        A naive recursive solution would recompute the same subproblems exponentially many times. For `nums = [1, 2, 3]` and `target = 100`, pure recursion would timeout.

        Either use top-down with memoisation, or bottom-up DP. Both achieve O(target × n) time complexity.
      wrong_approach: "Pure recursion: return sum(count(target - num) for num in nums)"
      correct_approach: "Memoisation or bottom-up DP to cache subproblem results"

  key_takeaways:
    - "**Loop order determines counting type**: Amounts-first counts permutations (order matters); items-first counts combinations (order ignored)"
    - "**Permutation counting via DP**: Sum the ways to reach all positions you could have come *from*"
    - "**Related to stair climbing**: This is essentially \"climb stairs\" with variable step sizes"
    - "**Foundation for string problems**: Same pattern applies to decode ways, word break counting, etc."

  time_complexity: "O(target × n). For each value from 1 to target, we iterate through all n numbers in the array."
  space_complexity: "O(target). The DP array stores one count per sum from 0 to target."

solutions:
  - approach_name: Bottom-Up DP
    is_optimal: true
    code: |
      def combination_sum4(nums: list[int], target: int) -> int:
          # dp[i] = number of ways to form sum i
          dp = [0] * (target + 1)

          # Base case: one way to make sum 0 (use nothing)
          dp[0] = 1

          # For each target sum, count ways to reach it
          for i in range(1, target + 1):
              # Try each number as the last element in the sequence
              for num in nums:
                  # If this number can contribute to sum i
                  if num <= i:
                      # Add all ways to form the remaining sum
                      dp[i] += dp[i - num]

          return dp[target]
    explanation: |
      **Time Complexity:** O(target × n) — Nested loops over target values and numbers.

      **Space Complexity:** O(target) — DP array of size `target + 1`.

      We build up counts from sum 0. For each sum `i`, we ask: "How many ways can I reach `i` by adding some number from `nums` to a smaller sum?" By summing `dp[i - num]` for all valid `num`, we count every possible sequence ending with that number.

  - approach_name: Top-Down DP (Memoisation)
    is_optimal: true
    code: |
      def combination_sum4(nums: list[int], target: int) -> int:
          # Cache for memoisation
          memo = {}

          def count(remaining: int) -> int:
              # Base case: found a valid sequence
              if remaining == 0:
                  return 1

              # Check cache
              if remaining in memo:
                  return memo[remaining]

              # Try each number as the next element
              total = 0
              for num in nums:
                  if num <= remaining:
                      total += count(remaining - num)

              # Cache and return
              memo[remaining] = total
              return total

          return count(target)
    explanation: |
      **Time Complexity:** O(target × n) — Each subproblem (0 to target) computed once, each checking n numbers.

      **Space Complexity:** O(target) — Memoisation cache plus recursion stack.

      This top-down approach is functionally equivalent to bottom-up. We recursively count ways to reduce `remaining` to 0, caching results to avoid recomputation. Some find this more intuitive as it directly mirrors the recurrence relation.
