⚡Flashcard Drill➔
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

  1. Let dp[t] be the number of ordered sequences summing to t, with dp[0] = 1 for the empty sequence.
  2. For each t from 1 to target and each value x <= t, add dp[t - x] to dp[t].
  3. Iterating the target in the outer loop and the values in the inner loop counts permutations, which is exactly what ordered sequences require.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems