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