Chapter 2 ended with a promise: the 0/1 Knapsack pattern unlocks a chain of problems that all look different on the surface but share the same structure underneath. Subset Sum is the first link in that chain.
When you first read the Subset Sum problem, it doesn't look like Knapsack at all. There's no value array. There's nothing to maximise. It just asks: can you find a subset that adds up to a target?
But look at the choices. For every element, you either include it or you don't. That's the same fork from Knapsack. The only thing that changed is what you're storing in the table and how you combine the two choices. Once you see that, Subset Sum takes about five minutes to understand. And Equal Sum Partition takes about two minutes after that.
The Subset Sum Problem
Given an array of positive integers and a target sum, does any subset of the array add up to exactly that target?
arr = [3, 3, 4, 12, 5, 2]
sum = 9
Possible: 3 + 4 + 2 = 9 → True
arr = [3, 34, 4, 12, 5, 2]
sum = 30
No subset adds to 30 → False
The answer is a boolean, not a number. That single difference is what separates it from Knapsack.
How Subset Sum Connects to 0/1 Knapsack
The choice diagram is identical. For every element, you have two options:
The structural difference comes at the combining step.
In Knapsack, you take the max() of the two choices because you want the best possible value.
In Subset Sum, you use or because you're asking a yes/no question. If either choice can produce the target sum, the answer is True. You don't need both to work. You just need one.
Knapsack: max(take, skip) → find the maximum value
Subset Sum: take OR skip → find any path that works
That one-word change (max to or) is the entire difference between the two problems.
The DP State
The table is defined the same way as Knapsack, adapted for the new question.
T[i][j] = Can I make sum j using the first i elements?
T[3][5] means: using only the first three elements of the array, is there any subset that adds up to 5?
The final answer lives at T[n][sum].
Initialisation: The Base Cases
Sum = 0: An empty subset always makes sum zero. So every cell in column 0 is True.
No elements: If you have zero elements and need a positive sum, it's impossible. Every cell in row 0 (except T[0][0]) is False.
# Sum 0 is always achievable with an empty subset
for i in range(n + 1):
T[i][0] = True
# No elements means no positive sum is possible
# T[0][0] stays True from the loop above
# T[0][1...sum] defaults to False from table initialisation
The Transition
For every cell T[i][j]:
If the current element fits (arr[i-1] <= j): check both choices. Include it (reduce the target by arr[i-1], look one row up) or exclude it (same target, look one row up). If either is True, this cell is True.
If the current element doesn't fit (arr[i-1] > j): only exclusion is possible. Copy the answer from the row above.
The Bottom-Up Solution
class Solution:
def isSubsetSum(self, arr, target):
n = len(arr)
# T[i][j] = can we make sum j using first i elements?
T = [[False] * (target + 1) for _ in range(n + 1)]
# Base case: sum 0 is always possible
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 the current element
T[i][j] = (
T[i - 1][j - arr[i - 1]] # include
or
T[i - 1][j] # exclude
)
else:
# Element too large — must exclude
T[i][j] = T[i - 1][j]
return T[n][target]
The Memoization Version
One important detail when writing the memoized version: you cannot use False as the "not yet calculated" placeholder. False is also a valid answer. The cache needs a third state that means "not computed yet."
Use None instead.
None → state not yet calculated
True → calculated, sum is possible
False → calculated, sum is not possible
class Solution:
def isSubsetSum(self, arr, target):
n = len(arr)
# None = not calculated yet
# Cannot use False — False is a valid answer
T = [[None] * (target + 1) for _ in range(n + 1)]
def solve(n, k):
# Base cases
if k == 0:
return True
if n == 0:
return False
# Return stored answer if already calculated
if T[n][k] is not None:
return T[n][k]
if arr[n - 1] <= k:
T[n][k] = (
solve(n - 1, k - arr[n - 1]) # include
or
solve(n - 1, k) # exclude
)
else:
T[n][k] = solve(n - 1, k) # must exclude
return T[n][k]
return solve(n, target)
Equal Sum Partition: One Observation Away
The problem: divide an array into two subsets such that both have equal sums.
arr = [1, 5, 11, 5]
S1 = [1, 5, 5] → sum = 11
S2 = [11] → sum = 11
True
At first glance this looks like a new problem. It isn't. Here's the key observation.
If the total sum of the array is R, and you want two equal subsets:
S1 + S2 = R
S1 = S2
→ S1 + S1 = R
→ 2 × S1 = R
→ S1 = R / 2
You don't need to find both subsets. Find one subset that sums to R/2. The remaining elements automatically form the second subset with the same sum.
Equal Sum Partition just became a Subset Sum problem.
The Odd Total Check
If the total sum is odd, equal partition is immediately impossible. You cannot split an integer array into two subsets each summing to a non-integer.
if total % 2 != 0:
return False
Always check this first. It avoids running the entire DP on an input that can't possibly work.
The Equal Sum Partition Code
class Solution:
def subsetSum(self, arr, target):
n = len(arr)
T = [[False] * (target + 1) for _ in range(n + 1)]
# Base case: sum 0 always possible
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:
T[i][j] = (
T[i - 1][j - arr[i - 1]]
or
T[i - 1][j]
)
else:
T[i][j] = T[i - 1][j]
return T[n][target]
def equalPartition(self, arr):
total = sum(arr)
# Odd total → equal partition is impossible
if total % 2 != 0:
return False
# Find one subset that sums to half the total
# The remaining elements form the second subset automatically
target = total // 2
return self.subsetSum(arr, target)
The Full Pattern So Far
Quick Revision
Subset Sum
T[i][j] = can I make sum j using first i elements?
If arr[i-1] <= j:
T[i][j] = T[i-1][j-arr[i-1]] or T[i-1][j]
If arr[i-1] > j:
T[i][j] = T[i-1][j]
Combine with OR, not max()
Use None (not False) as the memoization placeholder
Equal Sum Partition
total = sum(arr)
If total is odd → False
target = total // 2
Return SubsetSum(arr, target)
What You Now Understand
Two problems down in the Knapsack pattern chain. The structure stays the same: include or exclude, smaller subproblem, DP state, transition. What changes each time is the question being asked and the one-line operation that combines the two choices.
Knapsack asks for the maximum. Subset Sum asks for possibility. Equal Sum Partition asks for possibility after one mathematical reduction. The DP mechanics are nearly identical across all three.
Chapter 4 continues the chain with Count of Subsets: instead of asking "is it possible?", it asks "how many ways?" That shift from or to + is the next small change that opens the next set of problems.
Top comments (0)