Definition
- Partition Equal Subset Sum – determine if a positive integer array can be divided into two subsets with equal sums (LeetCode 416).
- Reduction – equivalent to asking whether some subset sums to exactly total / 2, because the complement automatically sums to the other half.
- 0/1 Knapsack – each number is used at most once. The downward sweep in the 1D DP enforces this.
- dp[s] – boolean indicating whether sum s is reachable from a subset of the numbers so far.
- Complexity – O(n * target) time, O(target) space.
An auditor at the National Bank of India wants to divide a set of settlement amounts into two piles of exactly equal total for a two-way reconciliation. If the grand total is odd, this is impossible. Otherwise she checks whether some combination of amounts reaches exactly half the total, because that half automatically leaves the other half behind.
Understanding the Concepts
What is the Partition Equal Subset Sum problem?
Given an array of positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. This is LeetCode 416.
For example, [1, 5, 11, 5] has total 22. Half is 11. The subset {1, 5, 5} sums to 11, and {11} sums to 11. So the answer is true.
package com.bank.service;
// Settlement amounts: [1000, 5000, 11000, 5000]
// Total: 22000, half: 11000
// Subset {1000, 5000, 5000} sums to 11000 -> can split equally
Why does this reduce to subset sum?
If any subset sums to total / 2, the remaining elements automatically sum to total - total / 2 = total / 2. So the problem is equivalent to: does a subset exist that sums to exactly half the total?
- Two early exits:
- If the total is odd, return false immediately. Two equal integer sums cannot add to an odd number.
- If the largest element exceeds half the total, return false.
package com.bank.service;
public class EarlyExits {
public static void main(String[] args) {
int[] odd = {1, 2, 4}; // total = 7, odd -> false
int[] big = {1, 2, 100}; // total = 103, odd -> false
// Also: [1, 2, 5] total=8, half=4, max=5 > 4 -> false
}
}
How does the DP solution work?
Create a boolean array dp of size target + 1 where target = total / 2. Initialize dp[0] = true because a sum of zero is always reachable by taking nothing. For each number in the array, sweep sums from target down to the number and set dp[s] = dp[s] || dp[s - num].
package com.bank.service;
public class PartitionEqualSubset {
public boolean canPartition(int[] nums) {
int total = 0;
for (int n : nums) total += n;
if (total % 2 != 0) return false;
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int s = target; s >= num; s--) {
dp[s] = dp[s] || dp[s - num];
}
}
return dp[target];
}
public static void main(String[] args) {
PartitionEqualSubset solver = new PartitionEqualSubset();
System.out.println(solver.canPartition(new int[]{1, 5, 11, 5})); // true
System.out.println(solver.canPartition(new int[]{1, 2, 3, 5})); // false
}
}
true
false
Why sweep downward?
The downward sweep is the classic 0/1 knapsack trick. If you swept upward (from num to target), dp[s - num] might have already been updated in this iteration, effectively using the same number twice. Sweeping downward ensures that dp[s - num] still reflects the state before the current number was considered.
// WRONG: upward sweep allows reuse (unbounded knapsack)
for (int s = num; s <= target; s++) {
dp[s] = dp[s] || dp[s - num]; // dp[s-num] may already include num
}
// CORRECT: downward sweep prevents reuse (0/1 knapsack)
for (int s = target; s >= num; s--) {
dp[s] = dp[s] || dp[s - num]; // dp[s-num] is from previous round
}
How do you trace the DP table?
For [1, 5, 11, 5] with target = 11:
- Initial: dp = [T, F, F, F, F, F, F, F, F, F, F, F] - After num=1: dp[1] = dp[0] = T -> dp = [T, T, F, F, F, F, F, F, F, F, F, F] - After num=5: dp[6] = dp[1] = T, dp[5] = dp[0] = T -> dp = [T, T, F, F, F, T, T, F, F, F, F, F] - After num=11: dp[11] = dp[0] = T -> dp = [T, T, F, F, F, T, T, F, F, F, F, T] - After num=5: dp[11] already T, dp[10] = dp[5] = T -> dp = [T, T, F, F, F, T, T, F, F, F, T, T] - dp[11] = true -> can partition!
package com.bank.service;
import java.util.Arrays;
public class DpTracer {
public static void main(String[] args) {
int[] nums = {1, 5, 11, 5};
int total = 22;
int target = 11;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int s = target; s >= num; s--) {
dp[s] = dp[s] || dp[s - num];
}
System.out.println("After num=" + num + ": " + Arrays.toString(dp));
}
System.out.println("Can partition: " + dp[target]);
}
}
After num=1: [true, true, false, false, false, false, false, false, false, false, false, false]
After num=5: [true, true, false, false, false, true, true, false, false, false, false, false]
After num=11: [true, true, false, false, false, true, true, false, false, false, false, true]
After num=5: [true, true, false, false, false, true, true, false, false, false, true, true]
Can partition: true
What are the edge cases?
- Single element: cannot partition (one side would be empty). But
[0]could partition if zero-sum subsets are allowed. - Two elements: partition only if they are equal.
- All zeros: always partitionable.
- Very large total: the DP table size is total / 2, which may be too large. Check constraints.
package com.bank.service;
public class PartitionEdgeCases {
public static void main(String[] args) {
PartitionEqualSubset solver = new PartitionEqualSubset();
System.out.println("[1]: " + solver.canPartition(new int[]{1})); // false
System.out.println("[3,3]: " + solver.canPartition(new int[]{3, 3})); // true
System.out.println("[1,1]: " + solver.canPartition(new int[]{1, 1})); // true
}
}
[1]: false
[3,3]: true
[1,1]: true
What about recovering the actual partition?
To find which elements form the subset, use a 2D boolean table dp[i][s] and backtrack: if dp[i][s] is true and dp[i-1][s] is false, then element i was included.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class PartitionRecovery {
public static List<Integer> findSubset(int[] nums, int target) {
int n = nums.length;
boolean[][] dp = new boolean[n + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int s = 0; s <= target; s++) {
dp[i][s] = dp[i - 1][s];
if (s >= nums[i - 1]) {
dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
}
}
}
List<Integer> subset = new ArrayList<>();
int s = target;
for (int i = n; i > 0 && s > 0; i--) {
if (!dp[i - 1][s]) {
subset.add(nums[i - 1]);
s -= nums[i - 1];
}
}
return subset;
}
public static void main(String[] args) {
int[] nums = {1, 5, 11, 5};
System.out.println("Subset: " + findSubset(nums, 11));
}
}
Subset: [11]
What about the banking domain use case?
At the National Bank of India, an auditor needs to split a batch of settlement amounts into two equal halves for a two-way reconciliation. She checks whether the total is even and whether a subset reaches half the total. The DP table gives the answer in O(n * target) time.
package com.bank.service;
public class ReconciliationSplitter {
public static void main(String[] args) {
int[] settlements = {3000, 7000, 5000, 5000};
PartitionEqualSubset solver = new PartitionEqualSubset();
boolean canSplit = solver.canPartition(settlements);
System.out.println("Can split settlements equally: " + canSplit);
}
}
Can split settlements equally: true
What are common interview follow-up questions?
- Why sweep downward? (To prevent using the same number twice: 0/1 knapsack trick.)
- What if the total is odd? (Return false immediately.)
- What is the time complexity? (O(n * target) where target = total / 2.)
- How do you recover the actual partition? (2D DP table with backtracking.)
- How does this relate to the knapsack problem? (It is the 0/1 knapsack feasibility variant with weights equal to values.)
Visual Overview
Partition Equal Subset Sum: [1, 5, 11, 5]
Total = 22, Target = 11
dp[0..11] boolean array:
Init: [T F F F F F F F F F F F]
After 1: [T T F F F F F F F F F F]
After 5: [T T F F F T T F F F F F]
After 11: [T T F F F T T F F F F T] ← dp[11]=true!
After 5: [T T F F F T T F F F T T]
dp[11] = true → a subset sums to 11 → can partition
Downward sweep ensures each number used at most once:
for (s = target; s >= num; s--)
dp[s] |= dp[s - num]
Key Takeaway
Partition Equal Subset Sum reduces cleanly to a subset-sum feasibility problem. The array can be split into two equal halves if and only if the total is even and some subset sums to exactly half the total, because that subset automatically leaves the other half behind.
The DP solution uses a boolean array where dp[s] means sum s is reachable. Initialize dp[0] = true, then for each number sweep sums downward from the target to the number, setting dp[s] = dp[s] || dp[s - num]. The downward sweep is the 0/1 knapsack trick that prevents reusing the same number.
At the National Bank of India, auditors need to split settlement batches into two equal halves for two-way reconciliation. The DP table determines whether an exact split exists in O(n * target) time, and the 2D variant with backtracking identifies which specific amounts go into each half.
The senior point is recognizing this as the 0/1 knapsack feasibility variant where weight equals value, and knowing that the 1D downward sweep optimizes space from O(n * target) to O(target). An odd total is rejected immediately without any computation.
Remember one sentence: check for even total, then use a downward-swept boolean DP to test if a subset reaches half.
---