Chapter 3 ended with a hint. The shift from Knapsack to Subset Sum was a one-word change: max() became or. The structure stayed identical. Only the question changed.
This chapter makes the next one-word change. Subset Sum asks "is it possible?" Count of Subsets asks "how many ways?" The answer shifts from a boolean to an integer. The DP table changes what it stores. And or becomes +.
That's the entire difference. Everything else is the same pattern you've already seen twice.
The Problem
Given an array and a target sum, count the number of subsets whose elements add up to exactly that target.
arr = [2, 3, 5]
sum = 5
Subsets that make 5:
[5] → 5
[2, 3] → 2 + 3 = 5
Answer = 2
Subset Sum would have returned True here. Count of Subsets returns 2. Same array. Same target. Different question.
The One Change That Separates These Two Problems
The choice diagram is identical. For every element, you include it or exclude it.
What changes is only the combining step:
| Problem | Question | Combine with |
|---|---|---|
| 0/1 Knapsack | Maximum value? | max() |
| Subset Sum | Is it possible? | or |
| Count of Subsets | How many ways? | + |
The same choice diagram. Three different questions. Three different one-word operations.
The DP State
T[i][j] = number of subsets using the first i elements
whose sum is exactly j
T[3][5] means: using only the first three elements, how many different subsets add up to 5?
The final answer sits at T[n][sum].
Initialisation: Where This Problem Gets Subtle
Here's where Count of Subsets needs more care than its predecessors.
T[0][0] represents zero elements and required sum zero. Exactly one subset achieves this: the empty subset {}. So:
T[0][0] = 1
For positive sums with zero elements, no subset is possible:
T[0][1...sum] = 0 # handled automatically by initialising the table to zero
The trap: In previous chapters, the base case was:
for i in range(n + 1):
T[i][0] = True # Subset Sum
Don't carry this into Count of Subsets. Do not write:
for i in range(n + 1):
T[i][0] = 1 # WRONG for arrays that contain zeros
Only initialise T[0][0] = 1 and let the normal transition fill the rest. Here is why.
The Zero Problem
When the array contains zeros, the initialisation above produces wrong answers.
arr = [0]
sum = 0
Subsets with sum 0:
{} → empty subset
{0} → includes the zero element
Answer = 2, not 1
arr = [0, 0]
sum = 0
Subsets with sum 0:
{}
{first 0}
{second 0}
{first 0, second 0}
Answer = 4
Every zero doubles the count. Because a zero element has two valid choices, include it (sum unchanged) or exclude it (sum unchanged), and both choices are valid.
The Transition
If arr[i-1] <= j:
T[i][j] = T[i-1][j-arr[i-1]] + T[i-1][j]
↑ ↑
include exclude
If arr[i-1] > j:
T[i][j] = T[i-1][j]
The Bottom-Up Solution
class Solution:
def perfectSum(self, arr, target):
n = len(arr)
# T[i][j] = number of subsets from first i elements
# whose sum equals j
T = [[0] * (target + 1) for _ in range(n + 1)]
# Only base case: empty subset makes sum 0 in exactly one way
T[0][0] = 1
for i in range(1, n + 1):
# Loop from 0 — zero elements must flow through
# the transition naturally, not be hard-coded
for j in range(target + 1):
if arr[i - 1] <= j:
# Count all ways from both choices
T[i][j] = (
T[i - 1][j - arr[i - 1]] # include
+
T[i - 1][j] # exclude
)
else:
# Element too large — must exclude
T[i][j] = T[i - 1][j]
return T[n][target]
Notice j starts from 0 in the inner loop, not from 1. In Subset Sum it started from 1 because T[i][0] = True was already set. Here it starts from 0 so zero-valued elements get processed through the transition correctly.
The Memoization Version
The same placeholder issue from Chapter 3 returns, with a new twist. You cannot use 0 as the "not yet computed" marker because 0 is a valid count.
None → state not yet calculated
0 → calculated, no valid subsets exist
1+ → calculated, this many valid subsets exist
class Solution:
def perfectSum(self, arr, target):
n = len(arr)
# None = not yet calculated
# 0 is a valid answer, so cannot use 0 as placeholder
T = [[None] * (target + 1) for _ in range(n + 1)]
def solve(n, k):
# Base cases
if n == 0 and k == 0:
return 1 # empty subset is one valid way
if n == 0:
return 0 # no elements left, positive sum impossible
# Return stored answer if already calculated
if T[n][k] is not None:
return T[n][k]
if arr[n - 1] <= k:
# Count ways from both choices
T[n][k] = (
solve(n - 1, k - arr[n - 1]) # include
+
solve(n - 1, k) # exclude
)
else:
T[n][k] = solve(n - 1, k) # must exclude
return T[n][k]
return solve(n, target)
The Mental Model You Should Carry Forward
This is the most important thing in this chapter. Not the code. Not the zero catch. This mental model.
Every time you see an include/exclude problem, ask one question first: what is the problem storing? The answer tells you the operation.
- Maximum value →
max() - Possibility →
or - Count →
+
You don't memorise three formulas. You memorise one structure and three questions.
Quick Revision
DP State
T[i][j] = number of subsets using first i elements with sum j
Initialisation
T[0][0] = 1 # only this — let zeros flow through the transition
Transition
# If current element fits:
T[i][j] = T[i-1][j-arr[i-1]] + T[i-1][j]
# If it doesn't fit:
T[i][j] = T[i-1][j]
The zero catch
arr = [0] → 2 subsets with sum 0
arr = [0, 0] → 4 subsets with sum 0
arr = [0, 0, 0] → 8 subsets with sum 0
Every zero doubles the count.
Don't hard-code T[i][0] = 1.
The memoization placeholder
None → not calculated
0 → calculated, zero ways
What You Now Understand
Four problems deep in the Knapsack pattern. The choices never changed. The structure never changed. What changed each time was a single operation: max(), or, +. Those three operations cover almost every variant of this pattern you'll encounter.
Chapter 5 continues with Minimum Subset Sum Difference, where the question shifts again: instead of finding a specific target, you want to minimise the gap between two subsets. The Subset Sum table you built here is exactly the tool that makes it possible.
Top comments (0)