Definition
Subset Sum is the feasibility core of the 0/1 Knapsack pattern.
- Boolean array
dp[t]records whether some subset of the numbers processed so far sums to exactlyt. - Base case is
dp[0] = truebecause the empty subset sums to zero. - Transition for each number sweeps targets from S down to the number:
dp[t] = dp[t] || dp[t - num]. - High-to-low sweep ensures each number is used at most once per subset.
- Time is O(N * S) and space is O(S) with the single-row optimization.
The National Bank of India has a list of individual transaction amounts and wants to know whether some combination of them exactly matches a disputed figure. Subset Sum checks, without trying every combination by brute force, whether any subset of charges reaches that exact amount.
Understanding the Concepts
What is the Subset Sum Problem?
Given a set of positive numbers and a target S, determine whether any subset of the numbers sums to exactly S. This is a decision problem: the answer is true or false.
At National Bank of India, the fraud team has a list of individual charges on a customer's account and a disputed total. They need to know if some combination of the charges exactly matches the disputed amount.
package com.bank.service;
public class SubsetSum {
public static boolean canReachTarget(int[] nums, int target) {
boolean[] dp = new boolean[target + 1];
dp[0] = true; // empty subset sums to zero
for (int num : nums) {
// Sweep from high to low to ensure each number used at most once
for (int t = target; t >= num; t--) {
if (dp[t - num]) {
dp[t] = true;
}
}
}
return dp[target];
}
public static void main(String[] args) {
int[] charges = {3000, 34000, 4000, 12000, 5000, 2000};
int disputed = 9000;
System.out.println("Can reach " + disputed + ": " + canReachTarget(charges, disputed));
// 4000 + 5000 = 9000 -> true
}
}
Can reach 9000: true
Why Does This Problem Matter?
Subset Sum is the pure feasibility variant of the 0/1 Knapsack. Understanding it unlocks a family of related problems: equal partition, minimum subset sum difference, target sum with plus and minus, and count of subsets with a given sum. It is also a classic NP-complete problem, which means no polynomial-time algorithm is known for arbitrary inputs.
package com.bank.service;
public class SubsetSumFamily {
// Subset Sum: can we hit target S? (this problem)
// Equal Partition: can we split into two equal halves? -> Subset Sum with S = total/2
// Min Subset Sum Diff: minimize |sum1 - sum2| -> find largest reachable sum <= total/2
// Count Subsets: how many subsets sum to S? -> change boolean to int count
}
How Does the Boolean DP Work?
We maintain a boolean array dp of size S+1, where dp[t] is true when some subset of the numbers processed so far sums to exactly t. We seed dp[0] = true because the empty subset sums to zero. For each number, we check whether adding it to an already-reachable sum creates a new reachable sum.
package com.bank.core;
public class SubsetSumTrace {
public static void main(String[] args) {
int[] nums = {3, 4, 5};
int target = 9;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
System.out.println("Processing number: " + num);
for (int t = target; t >= num; t--) {
if (dp[t - num] && !dp[t]) {
dp[t] = true;
System.out.println(" Marked dp[" + t + "] = true (from dp[" + (t - num) + "])");
}
}
}
System.out.println("Can reach " + target + ": " + dp[target]);
}
}
Processing number: 3
Marked dp[3] = true (from dp[0])
Processing number: 4
Marked dp[7] = true (from dp[3])
Marked dp[4] = true (from dp[0])
Processing number: 5
Marked dp[9] = true (from dp[4])
Marked dp[8] = true (from dp[3])
Marked dp[5] = true (from dp[0])
Can reach 9: true
Why Must the Sweep Go from High to Low?
The high-to-low sweep is the correctness guard that makes this 0/1 rather than unbounded. If we swept from low to high, a single number could be added to a sum it just created in the same pass, effectively using it multiple times.
package com.bank.core;
public class SweepDirection {
public static void main(String[] args) {
int[] nums = {3};
int target = 9;
// WRONG: low to high allows reuse
boolean[] dpWrong = new boolean[target + 1];
dpWrong[0] = true;
for (int t = 3; t <= target; t++) {
if (dpWrong[t - 3]) dpWrong[t] = true;
}
System.out.println("Low-to-high dp[9] = " + dpWrong[9]); // true (WRONG: 3 used 3 times)
// CORRECT: high to low prevents reuse
boolean[] dpRight = new boolean[target + 1];
dpRight[0] = true;
for (int t = target; t >= 3; t--) {
if (dpRight[t - 3]) dpRight[t] = true;
}
System.out.println("High-to-low dp[9] = " + dpRight[9]); // false (CORRECT: only one 3)
}
}
Low-to-high dp[9] = true
High-to-low dp[9] = false
How Is This Different from the 2D Approach?
The full 2D approach uses a table dp[i][t] where i is the number of items considered and t is the target sum. The 1D single-row approach optimizes space by observing that each row only depends on the previous row, so we can overwrite in place with the high-to-low sweep.
| Aspect | 2D Table | 1D Array |
|---|---|---|
| Space | O(N * S) | O(S) |
| Time | O(N * S) | O(N * S) |
| Reconstruction | Can trace back which items were chosen | Cannot trace without extra storage |
| Implementation | Two nested loops, clear dependency | Single array, must sweep high-to-low |
package com.bank.core;
public class SubsetSum2D {
public static boolean canReach2D(int[] nums, int target) {
int n = nums.length;
boolean[][] dp = new boolean[n + 1][target + 1];
for (int i = 0; i <= n; i++) dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int t = 1; t <= target; t++) {
dp[i][t] = dp[i - 1][t]; // skip current number
if (t >= nums[i - 1]) {
dp[i][t] = dp[i][t] || dp[i - 1][t - nums[i - 1]]; // take it
}
}
}
return dp[n][target];
}
}
What Are the Edge Cases?
The edge cases include: target is zero (always true via empty subset), target exceeds the total of all numbers (immediately false), all numbers are larger than the target (only dp[0] is true), and a single number equal to the target.
package com.bank.core;
public class SubsetSumEdgeCases {
public static void main(String[] args) {
// Target 0: always true
System.out.println(SubsetSum.canReachTarget(new int[]{5, 10}, 0)); // true
// Target > total: false
System.out.println(SubsetSum.canReachTarget(new int[]{1, 2, 3}, 100)); // false
// Single number equals target
System.out.println(SubsetSum.canReachTarget(new int[]{7}, 7)); // true
// All numbers larger than target
System.out.println(SubsetSum.canReachTarget(new int[]{10, 20}, 5)); // false
}
}
true
false
true
false
What About Early Termination?
We can exit early as soon as dp[target] becomes true, since we only need to know if the target is reachable. We can also check at the start whether the target exceeds the total sum of all numbers, returning false immediately.
package com.bank.core;
public class SubsetSumEarlyExit {
public static boolean canReachFast(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if (target > total) return false; // impossible
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int t = target; t >= num; t--) {
if (dp[t - num]) dp[t] = true;
}
if (dp[target]) return true; // early exit
}
return dp[target];
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Equal Partition: can the array be split into two subsets with equal sum? This is Subset Sum with target = total / 2.
- Count the number of subsets that sum to S: change the boolean array to an integer count array.
- Reconstruct which numbers form the subset: use the 2D table and trace back.
- What if numbers can be negative? The standard approach assumes positive numbers; negatives require shifting the index range.
package com.bank.core;
public class EqualPartition {
public static boolean canPartition(int[] nums) {
int total = 0;
for (int n : nums) total += n;
if (total % 2 != 0) return false; // odd total cannot split evenly
return SubsetSum.canReachTarget(nums, total / 2);
}
public static void main(String[] args) {
int[] amounts = {1000, 5000, 11000, 5000};
System.out.println("Can partition: " + canPartition(amounts));
// 1000 + 5000 + 5000 = 11000 = other half -> true
}
}
Can partition: true
Visual Overview
Subset Sum DP for nums = [3, 4, 5], target = 9:
Initial: dp = [T, F, F, F, F, F, F, F, F, F]
0 1 2 3 4 5 6 7 8 9
After 3: dp = [T, F, F, T, F, F, F, F, F, F]
0 3
After 4: dp = [T, F, F, T, T, F, F, T, F, F]
0 3 4 7
After 5: dp = [T, F, F, T, T, T, F, T, T, T]
0 3 4 5 7 8 9
dp[9] = true -> subset {4, 5} sums to 9
Sweep Direction (high to low):
┌────────────────────────────────────┐
│ t = 9, 8, 7, ..., num │
│ │
│ Reading from BEFORE this number │
│ was processed (left side of array) │
│ ensures each number used once. │
└────────────────────────────────────┘
Key Takeaway
Subset Sum is the pure feasibility core of the 0/1 Knapsack pattern. The question is simply whether any subset of the given numbers adds up to an exact target, and I answer it with a boolean DP array where each slot records whether that sum is reachable. I seed the array with dp[0] = true through the empty subset, then for every number I mark new sums reachable by extending sums that were already reachable.
The correctness hinge is the sweep direction. I iterate the target from high down to the current number so that within a single number's pass I never add that number to a sum it just created, which keeps each number usable at most once. This is the identical device that distinguishes 0/1 Knapsack from the unbounded variant. I also exit as soon as the target becomes reachable and reject instantly if the target exceeds the total.
At National Bank of India I used this in dispute reconciliation, where a customer claimed a specific total was charged and the fraud team needed to know whether some subset of the real individual charges summed exactly to that disputed figure. I ran the boolean subset-sum DP over the charge list toward the disputed target.
The family of problems built on this is large: equal partition (target = total/2), minimum subset sum difference, count of subsets with a given sum, and target sum with signs. All of them start from this same boolean reachability table.
Remember one sentence: seed dp[0] as true, sweep each number from high to low, and the answer is dp[target].
---