⚡Flashcard Drill➔
NeetCode #673LC-416Medium1-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems

#673 · #416 · Partition Equal Subset Sum(分割等和子集)

📌 Problem Statement & Constraints

Given a non-empty array nums of positive integers, return whether it can be partitioned into two subsets with equal sums. Constraints: 1 <= nums.length <= 200, 1 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. An equal partition exists only if the total sum is even; otherwise return false immediately.
  2. The problem reduces to a subset-sum question: find a subset whose sum equals half the total.
  3. Use a 1-D boolean DP over achievable sums, iterating sums downward so each element is used at most once (0/1 knapsack).
  4. dp[s] is true when some subset sums to s; the answer is dp[target].

💻 Benchmark Python3 Implementation

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False               # an odd total can never be split evenly
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for s in range(target, x - 1, -1):   # downward: 0/1 knapsack
                if dp[s - x]:
                    dp[s] = True
        return dp[target]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * target): the element count times half the total sum.
💾 Space Complexity
O(target): the boolean DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating the sum loop upward: that permits reusing one element repeatedly (unbounded knapsack); the downward loop enforces at most one use.
  • Skipping the odd-sum check: it is a cheap early exit and also avoids a fractional target.
  • Building a 2-D DP: correct but O(n * target) space for no benefit over the rolling array.
  • Assuming an even total guarantees a partition: [1, 2, 5] sums to 8 but no subset reaches 4.
⚡
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