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
numscontaining 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:
- 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.
- 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. - Reachability: If a number in
numscannot 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 (), which will time out given target up to 1000 and multiple branches per level.
We observe overlapping subproblems: To reach a specific sum , we could have come from any previous state by adding some number . Specifically, if we know the ways to form sum , 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 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).
- State Definition: Let
dp[i]be the number of combinations that sum to exactlyi. - Initialization: Create a list/array of size
target + 1, initialized with zeros, except fordp[0] = 1. The base case is crucial: there is one way to make a sum of zero (by choosing no numbers). - Transitions: Iterate through every integer from up to
target. For each index , iterate through all available numbers innums. If the current number fits (), we add the count of ways to form to our current state: - 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 using number , 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: , where is
nums.length. We iterate through each target value (up to 1000) and for each one, we check every number innums(up to 200). Total operations , which easily fits within standard time limits. - Space: 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 >= numensures 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.