NeetCode #677LC-377Medium1-D Dynamic ProgrammingNC 250
← Back to All Problems#677 · #377 · Combination Sum IV(组合总和 IV)
📌 Problem Statement & Constraints
Given an array of distinct positive integers
nums and a target, return the number of ordered sequences whose elements sum to target. Different orderings count as different sequences. Constraints: 1 <= nums.length <= 200, 1 <= nums[i] <= 1000, 1 <= target <= 1000.💡 Core Algorithmic Approaches
- Let
dp[t]be the number of ordered sequences summing tot, withdp[0] = 1for the empty sequence. - For each
tfrom 1 totargetand each valuex <= t, adddp[t - x]todp[t]. - Iterating the target in the outer loop and the values in the inner loop counts permutations, which is exactly what ordered sequences require.
- The answer is
dp[target].
💻 Benchmark Python3 Implementation
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1 # one way to make 0: the empty sequence
for t in range(1, target + 1):
for x in nums:
if x <= t:
dp[t] += dp[t - x]
return dp[target]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(target * len(nums)): the target loop times the value loop.
💾 Space Complexity
O(target): the DP array.
⚠️ Interview Pitfalls & Follow-ups
- Swapping the loop order: putting the values outside and the target inside counts each unordered combination once, which is problem 518 rather than this one.
- Forgetting
dp[0] = 1: every count would then be zero. - Deduplicating sequences:
[1, 1, 2]and[2, 1, 1]are distinct here and must both be counted. - Assuming the count fits in 32 bits: the problem guarantees it does, and Python integers are unbounded regardless.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.