Partition Equal Subset Sum
Reformulate the partition problem as a 0/1 knapsack on a target of total-sum/2, detecting feasibility with a boolean DP array.
Partition Equal Subset Sum is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Problem Statement
Given a non-empty array of positive integers nums, determine if you can partition it into two subsets with equal sum. For example, [1, 5, 11, 5] can be partitioned into [1, 5, 5] and [11], both summing to 11. If the total sum is odd, the answer is immediately False. Otherwise, we need to find a subset summing to total_sum // 2 — a classic subset sum problem.
Reduction to Subset Sum
The key reduction: if total sum S is even and a subset sums to S//2, the remaining elements automatically sum to S//2 as well. So Partition Equal Subset Sum reduces to: does any subset of nums sum to S//2? This is the classic NP-complete Subset Sum problem, which we solve with 0/1 knapsack DP in O(n × S) time.
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?Boolean DP Array
Define a boolean array dp[c] where dp[c] = True means a subset summing to exactly c exists. Initialise dp[0] = True (empty subset sums to 0) and all others False. For each number num, iterate capacity from target down to num (0/1 knapsack backward iteration) and set dp[c] = dp[c] or dp[c - num].
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # FalseTracing Through the Example
For [1, 5, 11, 5], total=22, target=11. Initially dp[0]=True. After num=1: dp[1]=True. After num=5: dp[5]=True, dp[6]=True. After num=11: dp[11]=True (using just 11 alone). We already found dp[11]=True — but we continue to process all numbers. Final answer: dp[11]=True, so partition is possible.
Early Termination Optimisation
We can add an early exit: if dp[target] becomes True at any point, immediately return True. This can dramatically speed up best-case scenarios. Also, if any single element equals target, we can return True immediately. If any single element exceeds target, it cannot be in any subset summing to target, but we still need to check the rest.
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # TrueUsing a Python Set Instead of DP Array
An alternative is to maintain a set of reachable sums. Start with {0}. For each number, add it to every sum in the current set: reachable = reachable | {s + num for s in reachable}. Filter to keep only sums that don't exceed target. At the end, check if target is in the set. This approach is intuitive but can use more memory and may be slower in practice.
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # TrueComplexity Analysis
The DP approach runs in O(n × S) time where S = sum(nums), and uses O(S) space for the boolean array. For the constraints in LeetCode (n ≤ 200, sum ≤ 20,000), this is at most 4,000,000 operations — very fast. The set approach has the same asymptotic complexity but may be slower in practice due to set construction overhead.
Generalising: Count Subsets with Sum
A related problem: count the number of subsets summing to a target. Change the DP from boolean to integer: dp[c] = number of ways to reach sum c. Use addition instead of OR: dp[c] += dp[c - num]. Initialise dp[0] = 1. Same backward iteration. This generalisation shows how the knapsack template adapts to different questions about subsets.
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))Common Interview Follow-Ups
Expect follow-up questions: (1) What if you need to return the actual partition? — requires 2D DP for reconstruction. (2) What if elements can be negative? — shift target, or use a dictionary instead of array. (3) What is the time complexity? — O(n × sum). (4) Can you improve if many numbers are the same? — yes, use frequency counting to reduce the number of outer iterations. Always mention these trade-offs proactively.
Connecting to 0/1 Knapsack
Partition Equal Subset Sum is a direct application of 0/1 knapsack: items are the numbers, weights equal values, and knapsack capacity equals target. We ask whether maximum value equals target (feasibility), not what the maximum value is. The backward iteration is the same, only the operation changes from max to boolean or. Recognising this connection in an interview demonstrates strong pattern recognition.
Edge Cases
Edge cases to handle: (1) array of length 1 — single element cannot be split, always False; (2) all elements identical and even count — may or may not work depending on individual values; (3) very large sums — check constraints before allocating the DP array; (4) elements larger than target — can be skipped (they can never be part of a subset summing to target). The max element check as early exit handles case (4) efficiently.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Partition Equal Subset Sum reduces to subset-sum with target = total//2, the boolean 1D DP dp[c] uses backward iteration identical to 0/1 knapsack, and the approach generalises to counting subsets by replacing boolean OR with integer addition. Next up we tackle Target Sum, transforming sign assignments into a knapsack on subset-sum difference.
Frequently asked questions
Is the “Partition Equal Subset Sum” lesson free?
Yes — the full text of “Partition Equal Subset Sum” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Partition Equal Subset Sum”?
Reformulate the partition problem as a 0/1 knapsack on a target of total-sum/2, detecting feasibility with a boolean DP array. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Partition Equal Subset Sum” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.