Domain 2MediumCORE

Combination Sum IV

The goal is to count the total number of ordered sequences (permutations) from nums that sum up exactly to target. Although titled 'Combination Sum IV', the examples clarify that order matters: (1, 2) and (2, 1) are distinct solutions.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

377. Combination Sum IV

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 46.2%


Problem Breakdown

The goal is to count the total number of ordered sequences (permutations) from nums that sum up exactly to target. Although titled “Combination Sum IV”, the examples clarify that order matters: (1, 2) and (2, 1) are distinct solutions.

Inputs:

  • An array nums containing unique positive integers.
  • A non-negative integer target.

Outputs:

  • The total count of valid sequences summing to target, guaranteed to fit in a standard 32-bit signed integer (though Python handles arbitrary precision automatically).

Implicit Constraints & Edge Cases:

  1. Order Sensitivity: Unlike “Coin Change” problems where order doesn’t matter, here we must treat every permutation as unique. This dictates the DP state transition logic.
  2. Base Case: A sum of 0 is achievable with an empty sequence (count = 1). We need to initialize dp[0] accordingly so that subsequent sums can build upon it.
  3. Reachability: If a number in nums cannot contribute to any valid path for the current target index, we simply skip adding its contribution.

Intuition

A brute-force approach using Depth-First Search (DFS) would explore every possible sequence recursively. For each step, we try subtracting every element from the remaining target until it hits zero or goes negative. However, this is exponential in complexity (O(NT)O(N^T)), which will time out given target up to 1000 and multiple branches per level.

We observe overlapping subproblems: To reach a specific sum ii, we could have come from any previous state jj by adding some number numnum. Specifically, if we know the ways to form sum (i−num)(i - num), then dp[i] increases by that count for every valid num.

This structure suggests Dynamic Programming. We define a 1D array where each index represents a specific target value and stores how many distinct sequences can reach it. By iterating through sums from 00 to target, we build the solution bottom-up, ensuring we reuse previously computed counts rather than recalculating them via recursion.

Approach

We use an iterative Dynamic Programming approach (Unbounded Knapsack style).

  1. State Definition: Let dp[i] be the number of combinations that sum to exactly i.
  2. Initialization: Create a list/array of size target + 1, initialized with zeros, except for dp[0] = 1. The base case is crucial: there is one way to make a sum of zero (by choosing no numbers).
  3. Transitions: Iterate through every integer from i=1i=1 up to target. For each index ii, iterate through all available numbers in nums. If the current number fits (num≤inum \le i), we add the count of ways to form (i−num)(i - num) to our current state: dp[i]+=dp[i−num]dp[i] += dp[i - num]
  4. Result: After filling the table, return dp[target].

Note on Order: Because we iterate through all numbers for each target index (rather than fixing an outer loop over coins), this approach naturally counts permutations where order matters. If (1, 2) is formed when processing sum 33 using number 22, and later processed again via a different path or logic, it ensures distinct sequences are counted correctly based on the last element added.

Complexity Analysis

  • Time: O(target×N)O(target \times N), where NN is nums.length. We iterate through each target value (up to 1000) and for each one, we check every number in nums (up to 200). Total operations ≈2⋅105\approx 2 \cdot 10^5, which easily fits within standard time limits.
  • Space: O(target)O(target) required to store the DP array of size target + 1.

Solution

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Initialize dp table where index represents sum value.
        # Base case: one way to make sum 0 (empty set).
        dp = [0] * (target + 1)
        dp[0] = 1
        
        # Iterate through each target sum from 1 up to the goal
        for i in range(1, target + 1):
            # Try adding every number in nums to reach current sum 'i'
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        
        return dp[target]

Edge Cases Handled

  • Target smaller than all elements: The loop condition if i >= num ensures we never access negative indices or add invalid paths; the result remains 0.
  • No valid combinations found: If no sequence sums to target, dp[target] will remain at its initialized value of 0 (unless base case logic is flawed).
  • Large counts: Python handles large integers automatically without overflow concerns common in languages like C++ or Java.