Chapter 5 reduced a two-subset problem to a one-number search using algebra. This chapter does the same thing, but this time the algebra hands you a direct answer instead of a search range.
The last chapter asked: which subset sum S1 minimises |R - 2S1|? This chapter asks: given that S1 - S2 = D, how many ways can that partition happen?
Different question. Same two equations. Same Count Subset Sum DP you already know.
The Problem
Given an array and a difference D, count the number of ways to divide the array into two subsets S1 and S2 such that S1 - S2 = D.
arr = [1, 1, 2, 3]
D = 1
Find all partitions where the difference between subset sums is exactly 1.
The Algebra (Again)
You've seen this setup before. Every element goes into either S1 or S2, so:
S1 + S2 = R (R = total sum)
S1 - S2 = D (given)
Add both equations:
S1 + S2 = R
S1 - S2 = D
───────────────
2S1 = R + D
S1 = (R + D) / 2
You don't need to find both subsets. Find one subset whose sum equals (R + D) / 2. Count how many such subsets exist. That count is your answer.
Count Subsets With Given Difference just became Count Subset Sum.
Two Checks Before You Touch the DP
Both of these need to pass before computing S1 = (R + D) / 2.
Check 1: |D| <= R
The maximum difference between two subsets is the total sum itself (one subset gets everything, the other gets nothing). If D exceeds R, the partition is impossible.
if abs(diff) > total:
return 0
Check 2: (R + D) must be even
S1 = (R + D) / 2 must be an integer because subset sums are always integers. If R + D is odd, no valid partition exists.
if (total + diff) % 2 != 0:
return 0
The DP: Count Subset Sum (Returning Again)
The transition is identical to Chapter 4. Store the count of subsets, combine with +, initialise only T[0][0] = 1, and loop j from 0 not 1.
class Solution:
def subsetSum(self, arr, subset):
n = len(arr)
# T[i][j] = number of subsets using first i elements
# whose sum is exactly j
T = [[0] * (subset + 1) for _ in range(n + 1)]
# Only base case: one way to make sum 0
# with zero elements — the empty subset
T[0][0] = 1
for i in range(1, n + 1):
# Start from 0 — zeros must flow through
# the transition naturally
for j in range(subset + 1):
if arr[i - 1] <= j:
# Count 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][subset]
def countPartitions(self, arr, diff):
total = sum(arr)
# Partition is impossible if difference exceeds total
if abs(diff) > total:
return 0
# S1 = (R+D)/2 must be an integer
if (total + diff) % 2 != 0:
return 0
# Directly calculated — no searching needed
subset = (total + diff) // 2
return self.subsetSum(arr, subset)
Target Sum: The Same Problem in Disguise
LeetCode's Target Sum problem asks something that looks completely different: given an array of numbers, assign a + or - sign to every element. Count the ways to reach a specific target.
nums = [1, 1, 2, 3]
target = 1
+1 -1 -2 +3 = 1 ✓
+1 +1 +2 -3 = 1 ✓
...
It feels like a sign-assignment problem. It isn't. It's two subsets in disguise.
Every element with a + sign belongs to S1. Every element with a - sign belongs to S2. The final expression S1 - S2 must equal target. That gives you:
S1 - S2 = target
S1 + S2 = total
→ S1 = (total + target) / 2
Count the subsets with sum S1. You're done.
Target Sum Code
The logic is identical to Count Partitions. Only the variable names change.
class Solution:
def subsetSum(self, nums, subset):
n = len(nums)
# T[i][j] = number of subsets using first i elements
# whose sum is exactly j
T = [[0] * (subset + 1) for _ in range(n + 1)]
# One way to make sum 0: empty subset
T[0][0] = 1
for i in range(1, n + 1):
# Start from 0 for correct zero handling
for j in range(subset + 1):
if nums[i - 1] <= j:
# Count both choices
T[i][j] = (
T[i - 1][j - nums[i - 1]] # include
+
T[i - 1][j] # exclude
)
else:
T[i][j] = T[i - 1][j]
return T[n][subset]
def findTargetSumWays(self, nums, target):
total = sum(nums)
# target cannot exceed the total range
if abs(target) > total:
return 0
# S1 = (total + target)/2 must be an integer
if (total + target) % 2 != 0:
return 0
# Same conversion as Count Partitions
subset = (total + target) // 2
return self.subsetSum(nums, subset)
Why These Two Problems Are Identical
Look at them side by side.
| Count Partitions | Target Sum | |
|---|---|---|
| Equation | S1 - S2 = D |
S1 - S2 = target |
| Total | S1 + S2 = R |
S1 + S2 = R |
| S1 | (R + D) / 2 |
(R + target) / 2 |
| Check 1 | `\ | D\ |
| Check 2 | {% raw %}(R + D) even |
(R + target) even |
| DP used | Count Subset Sum | Count Subset Sum |
The difference is semantic, not structural. One problem uses the word "difference," the other uses "target." The algebra is identical. The DP is identical.
The Full Knapsack Pattern Chain
Quick Revision
Count Partitions With Given Difference
S1 - S2 = D
S1 + S2 = R
→ S1 = (R + D) / 2
Check 1: abs(D) <= R → else return 0
Check 2: (R + D) % 2 == 0 → else return 0
subset = (R + D) // 2
return countSubsetSum(arr, subset)
Target Sum
+ elements = S1
- elements = S2
S1 - S2 = target
→ S1 = (R + target) / 2
Check 1: abs(target) <= R
Check 2: (R + target) % 2 == 0
subset = (R + target) // 2
return countSubsetSum(nums, subset)
Both reduce to Count Subset Sum with T[0][0] = 1 and loop starting from j = 0.
What You Now Understand
Six problems deep. The Knapsack chain is now complete for the 0/1 pattern. Every problem reused either Subset Sum or Count Subset Sum with one mathematical step in front of it. The algebra was the same twice: two equations, one variable, one direct target.
The pattern to carry forward is simple. When you see two subsets and a given difference, write S1 - S2 = D and S1 + S2 = R, add them, and you'll have the subset sum you need to count. The two checks (|D| <= R and (R + D) is even) guard against edge cases before the DP even starts.
The next part of the series moves into Unbounded Knapsack, where the structure shifts: instead of each item being available at most once, an item can be chosen as many times as needed. The choice diagram changes. The table direction changes. The core thinking stays exactly the same.
Top comments (0)