Subset Sum Problem: DP Table, Space Optimization & Edge Cases
The Subset Sum Problem shows up everywhere engineers don't expect it. Budget allocation engines, compiler register assignment, partition-based load balancing, and even fraud detection systems (flagging transactions that sum to known fraudulent totals) all reduce to some flavor of this problem. It's one of the 21 original NP-Complete problems identified by Karp in 1972 — meaning no polynomial-time solution is known for arbitrary inputs — yet with bounded integer weights, dynamic programming gives you a pseudo-polynomial solution that's fast enough for most real-world data. That nuance alone trips up experienced engineers in system design interviews.
The core tension is this: naive recursion explores every subset — 2ⁿ possibilities — which becomes catastrophically slow the moment your set grows past 30 elements. Dynamic programming reframes the question from 'which subsets?' to 'for every possible sum from 0 to W, can I reach it using elements up to index i?' That shift turns an exponential search into a table-filling exercise you can reason about cell by cell.
By the end of this article you'll be able to implement three versions of the solution — recursive with memoization, the classic 2D DP table, and the space-optimized 1D version — understand why the 1D version must iterate in reverse, correctly handle the all-zeros edge case and empty-subset semantics, and confidently answer the tricky follow-up questions interviewers use to separate good candidates from great ones.
Why Brute Force Fails and What Memoization Actually Saves
The recursive brute-force approach is elegant to write but brutal to run. At every index you make a binary choice: include this element in the current subset, or skip it. That gives you a binary tree of decisions with depth n — so the worst-case number of nodes is 2ⁿ. For n=40 that's over a trillion recursive calls. You will not wait for that to finish.
The saving grace is overlapping subproblems. When you're at index 3 trying to reach a remaining target of 12, it doesn't matter whether you got there by including element 0 or skipping it — the sub-problem is identical. Memoization caches the result of (index, remainingTarget) pairs so each unique pair is computed exactly once. The state space is n × (W+1), so time complexity drops to O(n·W) and space becomes O(n·W) for the cache plus O(n) for the call stack.
This is the conceptual bridge to full DP. Memoization is top-down DP — you start from the answer you want and recurse toward base cases, caching as you go. The 2D table is bottom-up DP — you start from base cases and build toward the answer. Both have the same asymptotic complexity; the table version avoids recursion overhead and stack overflow risk on large inputs, which matters in production.
import java.util.Arrays; public class SubsetSumMemoized { // memo[index][remainingTarget] = 1 (reachable), 0 (not reachable), -1 (unvisited) private static int[][] memo; public static void main(String[] args) { int[] numbers = {3, 34, 4, 12, 5, 2}; int target = 9; // Initialize memo table with -1 to signal "not yet computed" memo = new int[numbers.length][target + 1]; for (int[] row : memo) { Arrays.fill(row, -1); } boolean canReachTarget = hasSubsetWithSum(numbers, numbers.length - 1, target); System.out.println("Input: " + Arrays.toString(numbers)); System.out.println("Target: " + target); System.out.println("Subset exists: " + canReachTarget); // {4, 5} or {3, 4, 2} } /** * Top-down DP with memoization. * * @param numbers the input array * @param currentIndex we consider elements from index 0..currentIndex * @param remaining how much target sum is still needed * @return true if some subset of numbers[0..currentIndex] sums to remaining */ private static boolean hasSubsetWithSum(int[] numbers, int currentIndex, int remaining) { // Base case 1: remaining target is exactly 0 — empty subset achieves this if (remaining == 0) return true; // Base case 2: no elements left to consider and target not yet met if (currentIndex < 0) return false; // Base case 3: current element is larger than remaining target — can only skip it // (all elements assumed non-negative; including it would overshoot) if (numbers[currentIndex] > remaining) { if (memo[currentIndex][remaining] == -1) { memo[currentIndex][remaining] = hasSubsetWithSum(numbers, currentIndex - 1, remaining) ? 1 : 0; } return memo[currentIndex][remaining] == 1; } // Return cached result if available if (memo[currentIndex][remaining] != -1) { return memo[currentIndex][remaining] == 1; } // Core decision: skip the current element OR include it (subtract its value) boolean result = hasSubsetWithSum(numbers, currentIndex - 1, remaining) || hasSubsetWithSum(numbers, currentIndex - 1, remaining - numbers[currentIndex]); memo[currentIndex][remaining] = result ? 1 : 0; return result; } }
Target: 9
Subset exists: true
Building the 2D DP Table — Every Cell Explained
The bottom-up DP table is a boolean grid where dp[i][s] means: 'using only the first i elements of the array, can we form a subset that sums to exactly s?' Rows represent how many elements we've considered; columns represent every possible sum from 0 to W. Fill it left-to-right, top-to-bottom, and your final answer sits at dp[n][W].
The base cases anchor the table. dp[i][0] is true for every row because the empty subset always sums to zero — you can always choose nothing. dp[0][s] for s > 0 is false because with zero elements you can't reach any positive sum.
The recurrence is a direct translation of the recursive logic: dp[i][s] = dp[i-1][s] (skip element i) OR dp[i-1][s - nums[i-1]] (include element i, if s >= nums[i-1]). The 'include' branch looks back one row and looks left by the element's value. This is why you need the 2D table — you're always reading from the previous row, which remains untouched as you fill the current one.
Time complexity: O(n·W). Space complexity: O(n·W). For n=1000, W=10000, that's 10 million booleans — about 10 MB if stored as booleans, acceptable for most applications but worth profiling before you deploy.
import java.util.Arrays; public class SubsetSumDP2D { public static void main(String[] args) { int[] numbers = {3, 34, 4, 12, 5, 2}; int target = 9; boolean found = canAchieveTarget(numbers, target); System.out.println("Input: " + Arrays.toString(numbers)); System.out.println("Target: " + target); System.out.println("Subset with sum " + target + " exists: " + found); // Also print which subset was found by backtracking the table printSubset(numbers, target); } public static boolean canAchieveTarget(int[] numbers, int targetSum) { int n = numbers.length; // dp[i][s] = true means: using first i numbers, sum s is achievable boolean[][] dp = new boolean[n + 1][targetSum + 1]; // Base case: sum of 0 is always achievable (pick nothing) for (int i = 0; i <= n; i++) { dp[i][0] = true; } // Fill the table row by row (element by element) for (int i = 1; i <= n; i++) { int currentElement = numbers[i - 1]; // i-th element (1-indexed row, 0-indexed array) for (int sum = 1; sum <= targetSum; sum++) { // Option 1: skip the current element — inherit answer from previous row dp[i][sum] = dp[i - 1][sum]; // Option 2: include the current element, if it doesn't overshoot if (sum >= currentElement) { // If (sum - currentElement) was reachable without this element, now sum is reachable dp[i][sum] = dp[i][sum] || dp[i - 1][sum - currentElement]; } } } return dp[n][targetSum]; } /** * Backtracks through the filled DP table to reconstruct one valid subset. * This is a critical skill — the table tells you IF a solution exists; * backtracking tells you WHAT the solution is. */ public static void printSubset(int[] numbers, int targetSum) { int n = numbers.length; boolean[][] dp = new boolean[n + 1][targetSum + 1]; for (int i = 0; i <= n; i++) dp[i][0] = true; for (int i = 1; i <= n; i++) { int currentElement = numbers[i - 1]; for (int sum = 1; sum <= targetSum; sum++) { dp[i][sum] = dp[i - 1][sum]; if (sum >= currentElement) { dp[i][sum] = dp[i][sum] || dp[i - 1][sum - currentElement]; } } } if (!dp[n][targetSum]) { System.out.println("No valid subset found."); return; } // Backtrack: start from dp[n][target] and walk back to dp[0][0] int remainingSum = targetSum; System.out.print("One valid subset: {"); boolean first = true; for (int i = n; i > 0 && remainingSum > 0; i--) { // If dp[i][remainingSum] != dp[i-1][remainingSum], element i was INCLUDED if (!dp[i - 1][remainingSum]) { if (!first) System.out.print(", "); System.out.print(numbers[i - 1]); remainingSum -= numbers[i - 1]; // subtract included element and move left first = false; } // Otherwise, element i was skipped — move up the row without changing remainingSum } System.out.println("}"); } }
Target: 9
Subset with sum 9 exists: true
One valid subset: {5, 4}
Space-Optimized 1D DP — And Why You MUST Iterate in Reverse
The 2D table uses O(n·W) space, but notice that when computing row i you only ever read from row i-1 — never from earlier rows. That means you can collapse the entire table into a single 1D array and overwrite it in place, dropping space complexity to O(W).
Here's the catch that bites almost everyone: you must iterate the inner loop from right to left (from targetSum down to 1), not left to right. Here's why. In the 2D version, dp[i][sum - element] reads from row i-1 (the previous row). In the 1D version, if you iterate left-to-right, by the time you reach index sum, you may have already updated index (sum - element) in the current pass — meaning you'd be reading from the 'current row', not the 'previous row'. That's equivalent to allowing the same element to be used multiple times, which turns Subset Sum into the Unbounded Knapsack problem — a completely different problem with different answers.
Iterating right-to-left guarantees that when you read dp[sum - element], it still holds the value from the previous iteration (logically 'previous row'). This single-direction constraint is the most subtle and most tested aspect of this optimization. Get it wrong and your code produces wrong answers silently — no exceptions, no crashes, just incorrect results.
import java.util.Arrays; public class SubsetSumOptimized { public static void main(String[] args) { int[] numbers = {3, 34, 4, 12, 5, 2}; int targetSum = 9; System.out.println("Input: " + Arrays.toString(numbers)); System.out.println("Target: " + targetSum); System.out.println("Subset exists (space-optimized): " + canAchieveTargetOptimized(numbers, targetSum)); // Demonstrate the bug: left-to-right iteration gives wrong answer for certain inputs System.out.println("\n--- Demonstrating the left-to-right BUG ---"); int[] bugTestNumbers = {3, 5}; int bugTarget = 11; // NOT achievable — no subset of {3,5} sums to 11 System.out.println("Input: " + Arrays.toString(bugTestNumbers) + ", Target: " + bugTarget); System.out.println("Correct answer (right-to-left): " + canAchieveTargetOptimized(bugTestNumbers, bugTarget)); // false System.out.println("Buggy answer (left-to-right): " + canAchieveTargetBuggy(bugTestNumbers, bugTarget)); // true (wrong! uses 3 multiple times) } /** * CORRECT space-optimized solution. * Inner loop runs RIGHT TO LEFT to preserve previous-row semantics. */ public static boolean canAchieveTargetOptimized(int[] numbers, int targetSum) { // dp[s] = true means sum s is achievable using elements processed so far boolean[] dp = new boolean[targetSum + 1]; // Base case: sum 0 is always achievable (empty subset) dp[0] = true; for (int number : numbers) { // CRITICAL: iterate RIGHT TO LEFT so we don't reuse the same element // Reading dp[sum - number] must reflect the state BEFORE this element was considered for (int sum = targetSum; sum >= number; sum--) { // If (sum - number) was achievable before, now sum is achievable by including 'number' dp[sum] = dp[sum] || dp[sum - number]; } } return dp[targetSum]; } /** * BUGGY version — left-to-right iteration. * This silently solves Unbounded Knapsack instead of Subset Sum. * An element can be 'included' multiple times because we read updated values. */ public static boolean canAchieveTargetBuggy(int[] numbers, int targetSum) { boolean[] dp = new boolean[targetSum + 1]; dp[0] = true; for (int number : numbers) { // BUG: iterating left-to-right means dp[sum - number] may already // reflect the inclusion of 'number' earlier in this same pass. // Result: 'number' can be used more than once. for (int sum = number; sum <= targetSum; sum++) { dp[sum] = dp[sum] || dp[sum - number]; } } return dp[targetSum]; } }
Target: 9
Subset exists (space-optimized): true
--- Demonstrating the left-to-right BUG ---
Input: [3, 5], Target: 11
Correct answer (right-to-left): false
Buggy answer (left-to-right): true
| Approach | Time Complexity | Space Complexity | Handles Large n? | Reconstructs Subset? | Best Used When |
|---|---|---|---|---|---|
| Brute Force Recursion | O(2ⁿ) | O(n) stack | No — breaks at n≈30 | Yes, by tracking path | Never in production |
| Memoized Recursion (Top-Down) | O(n·W) | O(n·W) + O(n) stack | W-limited; stack risk at large n | Yes, with extra tracking array | W is small; prefer recursive style |
| 2D DP Table (Bottom-Up) | O(n·W) | O(n·W) | Yes — no stack risk | Yes, via backtracking | When you need subset reconstruction |
| 1D Space-Optimized DP | O(n·W) | O(W) | Yes — best for large n | No — original array lost | Production use, memory-constrained systems |
| Bitset Optimization | O(n·W/64) | O(W/64) | Yes — fastest for dense W | No | W up to ~10⁶; when raw speed matters |
🎯 Key Takeaways
- The 2D DP recurrence dp[i][s] = dp[i-1][s] OR dp[i-1][s-nums[i-1]] captures exactly two choices: skip element i or include it. Every other variant of this problem (knapsack, partition, target sum) is a transformation of this same recurrence.
- Right-to-left inner iteration in 1D DP is not a style choice — it's the mechanism that enforces 'each element used at most once'. Change direction and you silently solve a different problem. This distinction is one of the most common interview trip-wires at top-tier companies.
- The problem is pseudo-polynomial: O(n·W) looks polynomial but W is the numeric value of the target, not the number of bits used to represent it. If W=2^50, you're back to exponential time — this is precisely why Subset Sum remains NP-Complete despite having a DP solution.
- Backtracking a DP table to reconstruct the actual subset is a separate skill from filling the table. Practice the backtrack pattern: walk from dp[n][target] upward — if the value came from the row above unchanged, the element was skipped; if it changed, the element was included and you subtract its value from the remaining sum.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Iterating the 1D DP array left-to-right — Symptom: the function returns true for targets that require reusing an element (e.g., numbers={3,5}, target=9 returns true via 3+3+3, which is wrong for Subset Sum). No runtime error — just silently wrong results, which is the worst kind of bug. Fix: always iterate from targetSum down to number in the inner loop for 0/1 Subset Sum.
- ✕Mistake 2: Initializing dp[0] = false instead of true — Symptom: the entire DP table stays false because no sum is ever seeded as reachable, making the function always return false regardless of input. Fix: dp[0] must be true before the loop begins — the empty subset always achieves sum zero, and this seed is what propagates all reachability through the table.
- ✕Mistake 3: Assuming the problem only handles positive integers without validating — Symptom: if the input contains negative numbers or zeros, the dp array index (sum - element) can go negative, causing an ArrayIndexOutOfBoundsException. Or zeros cause silent logical errors where the element count changes without the target changing. Fix: validate input before running DP. If negatives are possible, shift all values by the absolute minimum to make them non-negative — but document this transformation clearly, as it changes the problem semantics.
Interview Questions on This Topic
- QThe Subset Sum Problem is NP-Complete — yet you just gave me an O(n·W) solution. Does that contradict the NP-Completeness claim? Why or why not?
- QIf I asked you to count ALL subsets that sum to the target (not just detect one), how would you modify the DP table? What changes in the recurrence and the base cases?
- QYou've implemented the 1D space-optimized version. Now I want to also return the actual subset elements, not just true/false. The 1D array doesn't store enough history to backtrack — how do you solve this without going back to the full O(n·W) 2D table?
Frequently Asked Questions
What is the difference between Subset Sum and the 0/1 Knapsack problem?
Subset Sum asks: can some subset of numbers sum to exactly W? The 0/1 Knapsack problem asks: what is the maximum value achievable within a weight limit W, where each item has both a weight and a value? Subset Sum is actually a special case of 0/1 Knapsack where every item's value equals its weight and you want to reach exactly W — not maximize. The DP structure is identical; only the objective function differs.
Can the Subset Sum Problem handle negative numbers?
The standard DP formulation assumes non-negative integers because array indices can't be negative. To handle negative numbers, shift all values by the absolute minimum (e.g., if the smallest element is -5, add 5 to every element and adjust the target accordingly). Alternatively, use a HashMap instead of an array to store reachable sums, which handles arbitrary integers without shifting — but at the cost of hash overhead and less cache efficiency.
Why does Subset Sum remain NP-Complete if dynamic programming solves it in O(n·W) time?
O(n·W) is pseudo-polynomial — it's polynomial in the numeric value of W, but W can be exponentially large relative to the number of bits needed to represent it. In complexity theory, input size is measured in bits, so an integer W requires only log₂(W) bits. If W = 2^1000, the algorithm is exponential in input size. NP-Completeness refers to the bit-complexity model, so there's no contradiction — the DP solution is only efficient when W is bounded by a polynomial in n.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.