Definition
Subset Sum with single-row optimization focuses on the space-efficient boolean DP.
- Single boolean row
dp[s]sized to target+1, seeded withdp[0] = true. - Reverse iteration for each number sweeps from target down to the number value.
- Transition
dp[s] = dp[s] || dp[s - num]extends reachable sums. - 0/1 guarantee comes from reading state from before the current number was processed.
- Early exit is possible the moment
dp[target]becomes true.
The National Bank of India must settle an exact outstanding amount by combining whole invoice payments, each used at most once. The team checks whether any combination of invoices sums precisely to the amount due, without trying every combination by brute force.
Understanding the Concepts
What is the Single-Row Subset Sum Optimization?
This problem is the same as the classic Subset Sum but focuses on the optimized single-row approach. Instead of a 2D table, we use a single boolean array and iterate in reverse. This reduces space from O(N * S) to O(S) while preserving the O(N * S) time complexity.
At National Bank of India, the settlement team needs to check if any combination of invoice amounts can exactly match an outstanding vendor payment.
package com.bank.service;
public class SubsetSumOptimized {
public static boolean canSum(int[] nums, int target) {
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int s = target; s >= num; s--) {
if (dp[s - num]) dp[s] = true;
}
if (dp[target]) return true; // early exit
}
return dp[target];
}
public static void main(String[] args) {
int[] invoices = {3000, 34000, 4000, 12000, 5000, 2000};
int outstanding = 9000;
System.out.println("Can settle " + outstanding + ": " + canSum(invoices, outstanding));
// 4000 + 5000 = 9000 -> true
}
}
Can settle 9000: true
Why Does Reverse Iteration Ensure Each Number Is Used Once?
When we iterate from target down to the number, we read dp[s - num] which still holds the value from before the current number was processed. If we iterated from low to high, dp[s - num] might already reflect the current number being added, effectively allowing the same number to be used multiple times.
This is the fundamental distinction between 0/1 Knapsack (high-to-low) and Unbounded Knapsack (low-to-high).
package com.bank.core;
public class ReverseIterationProof {
public static void main(String[] args) {
int num = 5000;
int target = 15000;
// HIGH-TO-LOW (correct for 0/1): each number used once
boolean[] dp1 = new boolean[target + 1];
dp1[0] = true;
for (int s = target; s >= num; s--) {
if (dp1[s - num]) dp1[s] = true;
}
System.out.println("High-to-low dp[15000] = " + dp1[15000]); // false (only one 5000)
System.out.println("High-to-low dp[5000] = " + dp1[5000]); // true
// LOW-TO-HIGH (wrong for 0/1): allows reuse
boolean[] dp2 = new boolean[target + 1];
dp2[0] = true;
for (int s = num; s <= target; s++) {
if (dp2[s - num]) dp2[s] = true;
}
System.out.println("Low-to-high dp[15000] = " + dp2[15000]); // true (5000 used 3 times)
}
}
High-to-low dp[15000] = false
High-to-low dp[5000] = true
Low-to-high dp[15000] = true
How Does This Compare to the 2D Table Approach?
The 2D approach uses dp[i][s] where i is the number of items considered and s is the sum. The 1D approach compresses this by observing that row i depends only on row i-1, so a single row suffices when swept in the right direction.
| Aspect | 2D Table | 1D Optimized |
|---|---|---|
| Space | O(N * S) | O(S) |
| Time | O(N * S) | O(N * S) |
| Sweep direction | Left-to-right in each row | Right-to-left (high-to-low) |
| Reconstruction | Trace back through table | Not possible without extra storage |
| Early exit | Check dp[N][S] at end | Check dp[S] after each number |
package com.bank.core;
public class SubsetSum2DFull {
public static boolean canSum2D(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 s = 1; s <= target; s++) {
dp[i][s] = dp[i - 1][s]; // skip this number
if (s >= nums[i - 1]) {
dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]]; // use this number
}
}
}
return dp[n][target];
}
}
What Is the Recursive Brute-Force Approach?
Before DP, the recursive approach tries including or excluding each number. This has exponential time O(2^N) but is useful for understanding the subproblem structure.
package com.bank.core;
public class SubsetSumRecursive {
public static boolean canSum(int[] nums, int index, int remaining) {
if (remaining == 0) return true; // found a valid subset
if (index >= nums.length || remaining < 0) return false;
// Include nums[index] OR exclude it
return canSum(nums, index + 1, remaining - nums[index])
|| canSum(nums, index + 1, remaining);
}
public static void main(String[] args) {
int[] invoices = {3000, 4000, 5000};
System.out.println(canSum(invoices, 0, 9000)); // true (4000 + 5000)
}
}
true
What Are the Edge Cases?
Edge cases include: target is zero (always true), single number equal to target (true), all numbers larger than target (false unless target is zero), and target exceeds total sum (immediately false).
package com.bank.core;
public class SubsetSumOptEdgeCases {
public static void main(String[] args) {
System.out.println(SubsetSumOptimized.canSum(new int[]{1, 2}, 0)); // true
System.out.println(SubsetSumOptimized.canSum(new int[]{7}, 7)); // true
System.out.println(SubsetSumOptimized.canSum(new int[]{10, 20}, 5)); // false
}
}
true
true
false
What About Non-Negative Integers Including Zero?
The title says non-negative, meaning zero can appear. A zero in the input does not change reachability: adding zero to any sum gives the same sum. However, it does affect the count of subsets (if counting), since including or excluding zero gives different subsets with the same sum.
package com.bank.core;
public class SubsetSumWithZero {
public static void main(String[] args) {
// Zero does not change reachability
int[] nums = {0, 3, 5};
System.out.println(SubsetSumOptimized.canSum(nums, 8)); // true (3 + 5)
System.out.println(SubsetSumOptimized.canSum(nums, 0)); // true (empty or {0})
}
}
true
true
What About Counting Subsets Instead of Boolean?
Changing the boolean array to an integer count array turns the decision problem into a counting problem. The transition becomes dp[s] += dp[s - num] instead of dp[s] = dp[s] || dp[s - num].
package com.bank.core;
public class SubsetSumCount {
public static int countSubsets(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = target; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[target];
}
public static void main(String[] args) {
int[] amounts = {1, 2, 3, 4, 5};
System.out.println("Subsets summing to 5: " + countSubsets(amounts, 5));
}
}
Subsets summing to 5: 3
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Equal Partition: can the array be split into two equal halves? Reduce to Subset Sum with target = total/2.
- Minimum Subset Sum Difference: find the partition with smallest difference.
- Target Sum with +/-: assign + or - to each number to reach a target.
- Count of subsets: change boolean to count.
- Reconstruct the subset: use the 2D table.
package com.bank.core;
public class SubsetSumFollowUps {
// Boolean -> Count: change || to +=
// Reachable -> Optimal: combine with value tracking
// 0/1 -> Unbounded: change sweep direction to low-to-high
}
Visual Overview
Single-Row Subset Sum DP:
nums = [3, 4, 5], target = 9
Initial: [T F F F F F F F F F]
0 1 2 3 4 5 6 7 8 9
After 3 (sweep 9 -> 3):
[T F F T F F F F F F]
0 3
After 4 (sweep 9 -> 4):
[T F F T T F F T F F]
0 3 4 7
After 5 (sweep 9 -> 5):
[T F F T T T F T T T]
0 3 4 5 7 8 9 <- dp[9] = true!
Reverse Sweep Guarantee:
┌──────────────────────────────────────┐
│ s = 9, 8, 7, ..., num │
│ We read dp[s-num] from LEFT side │
│ which has NOT been updated yet │
│ -> each number counted at most once │
└──────────────────────────────────────┘
Key Takeaway
Subset Sum with the single-row optimization is the space-efficient version of the classic boolean DP. I maintain a single boolean array of size target+1, seeded with dp[0] = true, and for each number I sweep from the target down to the number, marking new sums reachable. The reverse iteration is what guarantees each number is used at most once: I am always reading from the state before the current number was processed.
The key insight is that this is the boolean core of 0/1 Knapsack. The transition dp[s] = dp[s] || dp[s - num] says a sum is reachable if it was already reachable or if removing the current number gives a sum that was already reachable. The early exit optimization checks dp[target] after each number and returns immediately if it becomes true.
At the National Bank of India I used this in invoice settlement, where we needed to pay a vendor an exact outstanding amount by combining whole invoices, each paid in full or skipped. I ran the boolean subset-sum DP over the invoice amounts to confirm whether an exact combination existed before attempting settlement.
The space reduction from O(N * S) to O(S) is significant in practice. The tradeoff is that subset reconstruction requires the full 2D table. For counting subsets instead of just deciding reachability, change the boolean array to integers and || to +=.
Remember one sentence: a single boolean row swept from high to low ensures each number is used once, and dp[target] gives the answer.
---