Every chapter in this series has followed the same move: take the Knapsack structure, ask a different question, change one operation. Chapter 3 changed max() to or. Chapter 4 changed or to +. This chapter doesn't change the operation at all.
Instead, it adds a layer of mathematics on top of Subset Sum that reduces a problem about two subsets into a problem about one number on a number line.
Once the math clicks, the code is almost nothing new. You've already written it.
The Problem
Divide an array into two subsets S1 and S2 such that the absolute difference between their sums is as small as possible.
arr = [1, 6, 11, 5]
One possible partition:
S1 = [6, 5] → sum = 11
S2 = [1, 11] → sum = 12
|11 - 12| = 1
The answer for this array is 1.
The Mathematics That Unlocks the Problem
Before touching any DP, work out the algebra.
Every element goes into either S1 or S2. So:
S1 + S2 = R (R = total sum of the array)
You want to minimise |S1 - S2|. Substitute S2 = R - S1:
|S1 - S2|
= |S1 - (R - S1)|
= |2S1 - R|
= |R - 2S1|
The problem is now: find a possible subset sum S1 that minimises |R - 2S1|.
You don't need to explicitly construct either subset. You don't need to know which elements go where. You just need to know which values S1 can take. And that is exactly what Subset Sum answers.
The Number Line Intuition
Look at |R - 2S1|. As S1 increases from 0 toward R, the expression 2S1 moves from 0 toward 2R. The difference |R - 2S1| is smallest when S1 is closest to R/2.
0 ─────────────── R/2 ─────────────── R
↑
Ideal S1
(difference = 0 here)
The further S1 moves from the centre, the larger the difference grows. So the problem reduces to: among all possible subset sums, find the one closest to R/2.
Why You Only Check Half the Number Line
This is the part that confused earlier, so it gets its own section.
Suppose R = 22 and S1 = 8 is a possible subset sum. Then S2 = 14. The difference is |8 - 14| = 6.
Now flip the perspective. If instead you call the 14-element group S1, you get S1 = 14 and S2 = 8. The difference is still |14 - 8| = 6.
Every subset sum above R/2 is the mirror of a subset sum below R/2. They produce identical differences. Checking both is redundant.
So: run Subset Sum only up to target = R // 2. This is a search-space limit, not a claim that the answer must have a subset summing to exactly R/2.
target = R // 2
This means: "calculate possible sums from 0 to R//2 only."
It does NOT mean: "the answer must be R//2."
If no subset sums to exactly R//2, that's fine.
You want the closest possible value.
The Connection to Subset Sum
The complete reduction:
The Code
The Subset Sum function returns the entire last row of the DP table — every possible subset sum up to target — rather than a single boolean. The minimum difference function uses that row to find the best S1.
class Solution:
def subsetSum(self, arr, target):
n = len(arr)
# T[i][j] = True if sum j is achievable
# using first i elements
T = [[False] * (target + 1) for _ in range(n + 1)]
# Sum 0 is always possible — empty subset
for i in range(n + 1):
T[i][0] = True
for i in range(1, n + 1):
for j in range(1, target + 1):
if arr[i - 1] <= j:
# Include OR exclude current element
T[i][j] = (
T[i - 1][j - arr[i - 1]]
or
T[i - 1][j]
)
else:
# Can't include — must exclude
T[i][j] = T[i - 1][j]
# Return the last row — all possible sums for n elements
# up to target
return T[n]
def minDifference(self, arr):
# Total sum R
R = sum(arr)
# Only need subset sums up to R//2
# (mirror symmetry makes the other half redundant)
target = R // 2
# Get all possible subset sums from 0 to target
possible = self.subsetSum(arr, target)
minimum = float('inf')
# Check every possible S1 from 0 to R//2
for S1 in range(target + 1):
if possible[S1]:
# S2 = R - S1
# |S1 - S2| = |R - 2*S1|
diff = abs(R - 2 * S1)
minimum = min(minimum, diff)
return minimum
Walking Through the Example
arr = [1, 6, 11, 5]
R = 1 + 6 + 11 + 5 = 23
target = 23 // 2 = 11
After running Subset Sum up to 11, the possible row looks like:
sum: 0 1 2 3 4 5 6 7 8 9 10 11
possible: T T F F F T T T F F F T
Now check each possible S1:
S1 = 0 → |23 - 0| = 23
S1 = 1 → |23 - 2| = 21
S1 = 5 → |23 - 10| = 13
S1 = 6 → |23 - 12| = 11
S1 = 7 → |23 - 14| = 9
S1 = 11 → |23 - 22| = 1 ← minimum
Answer: 1.
The subset summing to 11 is [11]. The remaining elements [1, 6, 5] sum to 12. Difference is 1.
The One Mistake to Avoid
target = R // 2 is easy to misread. Here is what it does and does not mean:
target = R // 2
DOES mean: "only calculate subset sums from 0 to R//2."
This is a search-space optimisation.
DOES NOT mean: "there must exist a subset whose sum is R//2."
There might be no such subset — that's fine.
You're looking for the closest possible value.
If R = 23 and no subset sums to 11, you simply check all the sums that do exist (say 10 and 7) and return the minimum difference among those. The // is integer division because subset sums are always integers. R/2 = 11.5 is unreachable so 11 is the highest integer worth checking.
The Full Chain So Far
Quick Revision
The core math
S1 + S2 = R
|S1 - S2| = |R - 2S1|
Goal: find S1 that minimises |R - 2S1|
The DP strategy
Run Subset Sum up to target = R // 2
Get all possible S1 values
For each possible S1: compute |R - 2S1|
Return the minimum
The target clarification
target = R // 2 is a search-space limit
It is NOT the required subset sum
The closest achievable S1 to R/2 is the answer
When to recognise this pattern
"Divide into two subsets, minimise difference"
↓
S1 + S2 = R
↓
|R - 2S1|
↓
Subset Sum DP
What You Now Understand
Five problems into the Knapsack chain. Each one reused the structure from the previous chapter and added one idea: a different operation, a mathematical trick, or a search-space insight. Minimum Subset Sum Difference added the algebra that collapses a two-subset problem into a one-number search.
Chapter 6 continues with Target Sum, where the question changes again: instead of minimising a difference, you assign + or - signs to elements and count the ways to reach a specific target. The Subset Sum table returns, and a new mathematical reduction makes it possible.
The pattern keeps building. The new code keeps shrinking.
Top comments (0)