Subset Sum & Partition
Reach a target with a chosen subset.
Subset Sum & Partition is a free Coding Interview Prep lesson on CoddyKit — lesson 4 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 Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Subset Sum Question
Given numbers and a target, can any subset add up to exactly that target? It is knapsack where value equals weight.
Boolean DP, Not Value
Here you track reachability, not a maximum. Let dp[s] be True when some subset sums to exactly s.
dp = [False] * (target + 1)
dp[0] = TrueZero Is Always Reachable
The empty subset sums to zero, so dp[0] starts True. Every other sum begins False until a number proves it reachable.
The Transition
For each number, mark s reachable if s - num already was. One number can flip many sums to True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Backward Again
Each number is used at most once, so the inner loop runs backward, just like 0/1 knapsack. Forward would reuse a number.
Read the Verdict
After processing all numbers, dp[target] answers the question. True means a valid subset exists; False means it is impossible.
Enter Partition
The partition problem asks: can you split the array into two halves of equal sum? It reduces straight to subset sum.
Halve the Total
If the total sum is odd, equal halves are impossible, so answer no at once. Otherwise the target is simply total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Reuse Subset Sum
Now just ask if a subset reaches total // 2. If one half hits the target, the rest forms the matching second half automatically.
The Complexity
The cost is order n times target, a pseudo-polynomial bound. It is fast when the target is small, slow when sums are huge.
One Family of Problems
Subset sum, partition, and 0/1 knapsack share one engine. Spot the take-or-leave shape and you reuse the same loop.
Quick Check
Test the partition reduction.
Recap
You solved subset sum with boolean DP and a backward loop, then reduced partition to hitting total // 2. Same engine, new wins. ✅
Frequently asked questions
Is the “Subset Sum & Partition” lesson free?
Yes — the full text of “Subset Sum & Partition” is free to read here on the web, and the Coding 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 Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Subset Sum & Partition”?
Reach a target with a chosen subset. You practise Coding 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 Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Subset Sum & Partition” 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 Coding Interview Prep lesson?
Yes. Every Coding 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.
All lessons in this course
- 0/1 Knapsack: Take or Leave
- Space-Optimized Knapsack
- Unbounded & Coin-Change DP
- Subset Sum & Partition