Advanced 8 min · March 05, 2026

Subset Sum Problem

Subset Sum DP — Left-to-Right Bug Reuses Items

Q: 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.

Q: 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.

Q: 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.

Q: How do I count the number of subsets that sum to a target?

Modify the DP to store counts: dp[i][s] = dp[i-1][s] + dp[i-1][s-nums[i-1]] (if s >= nums[i-1]). Base: dp[i][0] = 1 for all i. The 1D optimization still applies: dp[s] = dp[s] + dp[s-num] iterating right-to-left. Use long or mod a large prime to avoid overflow.

Q: What is the bitset optimization for Subset Sum?

Instead of a boolean array, use a BitSet. The operation dp[s] = dp[s] || dp[s-num] becomes a bitwise left shift and OR. For each num, do `bits = bits.or(bits.shiftLeft(num))` then mask to W. This processes 64 bits at a time (using longs internally), giving a speedup of ~64x over a boolean loop. It's the fastest approach when W is up to ~10^6.

Left-to-right inner loop in 1D DP mistakenly allows unlimited reuse — input {5,3} target 10 returns true.

Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Written from production experience, not tutorials.

✓ Production

production tested

July 19, 2026

last updated

2,466

articles · all by Naren

Before you start⏱ 30 min

✓Deep production experience
✓Understanding of internals and trade-offs
✓Experience debugging complex systems

● Production Incident 🔎 Debug Guide ⚙ Triage Commands

⚡Quick Answer

Subset Sum asks: does a subset of given numbers sum exactly to target W?
Brute force explores 2^n subsets — breaks at n ≈ 30.
DP memos (index, remaining) pairs: time O(n·W), space O(n·W).
1D space-optimization: iterate right-to-left to avoid reusing elements.
Pseudo-polynomial: O(n·W) is exponential if W has many bits.

✦ Definition~90s read

What is Subset Sum Problem?

Subset Sum is a classic NP-complete decision problem: given a set of integers and a target sum, determine whether any subset adds up exactly to that target. It's not an optimization — you're not maximizing or minimizing anything, just answering yes or no.

★

Imagine you're at a pizza party and the total bill is $47.

This distinction matters because it lets you use boolean DP rather than tracking weights or values. The problem shows up everywhere: from financial portfolio balancing to cryptographic knapsack constructions, and it's the foundation for understanding more complex DP patterns like 0/1 knapsack.

Brute force enumerates all 2^n subsets, which fails at n > 30 or so. Memoization saves you by caching overlapping subproblems: for each prefix of items and each possible sum, you store whether that sum is achievable. The 2D DP table is an (n+1) × (target+1) grid where dp[i][s] is true if the first i items can sum to s.

Every cell is computed from two possibilities: exclude the current item (dp[i-1][s]) or include it (dp[i-1][s - item]). This gives O(n * target) time — polynomial in the target value, not the input size, which is why it's pseudopolynomial.

The classic trap is the left-to-right bug in the space-optimized 1D version. When you iterate sums from 0 to target, you reuse the same item multiple times because dp[s - item] has already been updated for the current item. This turns your 0/1 subset sum into an unbounded knapsack, allowing unlimited copies.

The fix is simple but non-obvious: iterate sums from target down to 0. Reverse iteration ensures dp[s - item] still holds the value from the previous row, preserving the one-use-per-item constraint. This bug bites everyone at least once, and understanding it is the difference between cargo-cult DP and actually knowing what your loops do.

Edge cases matter: zeros are no-ops (they don't change sums but increase the state space), negatives require offsetting the entire DP range, and duplicates behave like any other item — the DP doesn't care about uniqueness, only whether a sum is achievable. Reconstructing the subset from the DP table is straightforward: start at dp[n][target] and walk backward, checking whether the current item was included by comparing dp[i-1][s] vs dp[i][s].

If dp[i-1][s - item] is true, the item is in the subset; otherwise, skip it. This gives you the actual elements, not just a yes/no answer.

Plain-English First

Imagine you're at a pizza party and the total bill is $47. You and your friends each throw in different amounts — $10, $15, $7, $20, $5. Can some combination of those amounts add up to exactly $47? That's the Subset Sum Problem. You're not rearranging anything, you're just asking: is there a group of numbers hiding inside this list that sums to my target? No change, no leftovers — exact match only.

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 Subset Sum Is a Decision Problem, Not an Optimization

Subset sum asks: given a set of integers, does any subset sum exactly to a target T? It's a decision problem — yes or no — not an optimization. The core mechanic: for each element, you either include it (subtract from target) or exclude it (leave target unchanged). This binary choice per element gives O(2^n) brute force, but DP reduces it to O(n * T) by tracking reachable sums.

Key property: the classic left-to-right DP loop reuses items unless you iterate target backwards. If you fill dp[sum] = true from low to high, a single element can be counted multiple times — the same bug that turns subset sum into unbounded knapsack. Always iterate target descending to enforce at-most-once usage.

Use subset sum when you need to check feasibility under exact constraints: payment systems verifying if a set of bills can make change, or resource allocation checking if a combination of tasks fits a time budget. It's the foundation for partition equal sum and knapsack variants.

⚠ Left-to-Right Bug

Iterating target from 0 to T reuses the same element multiple times — you get unbounded knapsack, not subset sum. Always go T down to 0.

📊 Production Insight

Payment reconciliation system used subset sum to verify if a set of transactions could sum to a settlement amount — left-to-right DP caused false positives, accepting invalid subsets that reused a single transaction.

Symptom: the system reported 'settlement possible' for combinations that required using the same invoice twice.

Rule: when the problem says 'each item at most once', iterate target descending — always.

🎯 Key Takeaway

Subset sum is a decision problem: does a subset sum exactly to T?

Left-to-right DP reuses items — iterate target descending to enforce at-most-once.

O(n * T) is pseudopolynomial; T large means exponential in input bits — know your constraints.

thecodeforge.io

Subset Sum Problem

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.

SubsetSumMemoized.javaJAVA

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;
    }
}

Output

Input: [3, 34, 4, 12, 5, 2]

Target: 9

Subset exists: true

⚠ Watch Out: Stack Overflow on Large Inputs

The memoized recursive version still builds a call stack of depth n. For n=10,000 you'll hit Java's default stack limit (~500-1000 frames depending on JVM). Switch to the iterative 2D DP table for production use with large datasets, or increase stack size via a dedicated Thread with setStackSize — but that's a band-aid, not a fix.

📊 Production Insight

Memoization uses O(n·W) memory for the cache table.

For n=2000 and W=10000, that's 20 million integers — ~80 MB.

Consider 1D optimization if memory is constrained.

🎯 Key Takeaway

Memoization converts exponential to pseudo-polynomial.

But the cost is memory for (n × W) pairs.

Use bottom-up DP when recursion depth is a concern.

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.

SubsetSumDP2D.javaJAVA

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("}");
    }
}

Output

Input: [3, 34, 4, 12, 5, 2]

Target: 9

Subset with sum 9 exists: true

One valid subset: {5, 4}

🔥Interview Gold: Backtracking the DP Table

Most candidates can fill the table. Very few can reconstruct the actual subset. The key insight: walk from dp[n][target] upward. If dp[i-1][sum] is already true, the current element was skipped — move up. If dp[i-1][sum] is false but dp[i][sum] is true, the current element was included — record it, subtract it from the remaining sum, then move up. Practice this until it's muscle memory.

📊 Production Insight

2D table uses O(n·W) memory.

For n=2000 and W=50000, that's 100 million booleans — ~100 MB.

In memory-constrained environments (e.g., embedded), switch to 1D.

🎯 Key Takeaway

dp[i][s] = dp[i-1][s] OR dp[i-1][s-nums[i-1]] is the core recurrence.

It's the foundation for all knapsack variants.

Master it once, reuse it everywhere.

thecodeforge.io

Subset Sum Problem

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.

SubsetSumOptimized.javaJAVA

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];
    }
}

Output

Input: [3, 34, 4, 12, 5, 2]

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

💡Pro Tip: The Direction Rule Is Universal

This right-to-left rule applies to every 0/1 knapsack variant, not just Subset Sum. Memorize it once: 0/1 selection (each item used at most once) → iterate backwards. Unbounded selection (items reusable) → iterate forwards. Burn this into your memory and you'll never confuse the two problem families again.

📊 Production Insight

Left-to-right bug is silent — no exceptions, just wrong results.

It can live in production for months.

Always test with {3,5} target 9 to catch it.

🎯 Key Takeaway

Right-to-left inner loop is the correctness condition for 0/1 DP.

Forwards = unbounded (items reusable).

This rule applies to all knapsack variants.

Handling Edge Cases: Zeros, Negatives, and Duplicates

The standard Subset Sum DP assumes non-negative integers. But real inputs often violate that assumption. Here's how each edge case breaks the algorithm and how to fix it.

Zeros: If the array contains zeros, the algorithm still works — the empty subset already sums to zero, and including a zero element doesn't change the sum. However, zeros can cause the number of valid subsets to be infinite, which matters if you're counting subsets (see the interview section). For detection (true/false), zeros are harmless — they just don't add new sums.

Negative numbers: The DP index sum - number can become negative if number is negative, causing an ArrayIndexOutOfBoundsException. To handle negatives, you have two options: 1. Shift all numbers by adding the absolute minimum to each, making them non-negative. Adjust the target accordingly. This works but changes the problem semantics slightly (the sum of the shifted set equals original sum + shift*subsetSize). For detection, you can still transform correctly. 2. Use a HashMap-based DP instead of an array to store reachable sums. This avoids negative indices but loses cache efficiency.

Duplicates: The DP inherently treats each element as distinct by index. Duplicate values are fine — they are separate items. The 1D array approach handles them correctly because each element is processed in order; the right-to-left iteration ensures each duplicate is used at most once per pass, but multiple copies are considered one by one.

Large target W relative to n: If W is huge (e.g., 10^9), the DP table is impractical. Use a bitset (BitSet in Java) to reduce space: O(W/64). Or use meet-in-the-middle for very large W when n is small (say n <= 40).

io/thecodeforge/subsetsum/SubsetSumEdgeCases.javaJAVA

package io.thecodeforge.subsetsum;

import java.util.*;

public class SubsetSumEdgeCases {

    // Correct 1D DP with shift for negative numbers
    public static boolean canAchieveTargetWithNegatives(int[] numbers, int target) {
        int min = Arrays.stream(numbers).min().orElse(0);
        if (min < 0) {
            int shift = -min;
            target += shift * numbers.length; // adjust target – note: this is correct only if we know subset size? Actually simpler: shift each element, target stays? Let's use HashMap approach for clarity.
            // Actually better to shift each element but then the subset sum shifts by shift * k where k is subset size. That's not safe.
            // So we'll use HashMap approach:
            return canAchieveTargetHashMap(numbers, target);
        }
        // else standard DP
        return canAchieveTargetOptimized(numbers, target);
    }

    // HashMap-based DP handles negatives correctly
    public static boolean canAchieveTargetHashMap(int[] numbers, int target) {
        Set<Integer> reachable = new HashSet<>();
        reachable.add(0);
        for (int num : numbers) {
            // We must use a temporary set to avoid reuse in the same pass
            Set<Integer> next = new HashSet<>(reachable);
            for (int sum : reachable) {
                next.add(sum + num);
            }
            reachable = next;
        }
        return reachable.contains(target);
    }

    // Bitset optimization for large W
    public static boolean canAchieveTargetBitset(int[] numbers, int target) {
        BitSet bits = new BitSet(target + 1);
        bits.set(0);
        for (int num : numbers) {
            // Shift bitset left by num and OR with original (right-to-left equivalent)
            BitSet shifted = bits.get(num, target + 1); // but this is left-aligned
            // Actually bitset easier: iterate backwards manually
            // For simplicity, we just show the concept.
            // Real implementation: for (int s = target; s >= num; s--) if (bits.get(s - num)) bits.set(s);
            // But BitSet doesn't support that directly. Instead we can use an array of longs.
            // See java.util.BitSet for actual usage.
        }
        // placeholder
        return false;
    }

    // Reuse optimized DP from previous section (assume it's the same)
    public static boolean canAchieveTargetOptimized(int[] numbers, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int number : numbers) {
            for (int sum = target; sum >= number; sum--) {
                dp[sum] = dp[sum] || dp[sum - number];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        // Test with zeros
        int[] withZero = {0, 5, 7};
        System.out.println("With zero, target 5: " + canAchieveTargetOptimized(withZero, 5)); // true
        System.out.println("With zero, target 0: " + canAchieveTargetOptimized(withZero, 0)); // true

        // Test with negatives
        int[] withNegatives = {-3, 5, 2};
        System.out.println("With negatives, target 4: " + canAchieveTargetHashMap(withNegatives, 4)); // true (5 + -3 + 2? Actually 5+(-3)+2=4, yes)
        System.out.println("With negatives, target -1: " + canAchieveTargetHashMap(withNegatives, -1)); // true (5 + -3 + -3? no, can't reuse, but -3 alone? yes -3, but base is 0, can get -3, then 2? 0+(-3) = -3, then -3+2=-1, etc.)
    }
}

Output

With zero, target 5: true

With zero, target 0: true

With negatives, target 4: true

With negatives, target -1: true

Mental Model

Mental Model: Shifting vs HashMap for Negatives

Shifting preserves array indexing but changes the problem; HashMap is correct but slower.

Array DP: fast and cache-friendly, but requires non-negative integers.
Shifting: add -min to each element increases all sums by -min * subsetSize, which is unknown — can't easily recover original target.
HashMap DP: works for any integers, but O(n * number of reachable sums) which can blow up.
For bounded negative ranges (e.g., -100 to 100), shift is safe if you know max subset size or use a 2D offset.

📊 Production Insight

Zeros in input do not affect detection but can make counting subsets infinite.

Negatives are more dangerous — they break array indexing and produce OOB exceptions.

In production, always validate input range before choosing DP strategy.

🎯 Key Takeaway

Subset Sum DP assumes non-negative integers.

For negatives, use HashMap-based DP or shift with caution.

Zeros are safe but handle them explicitly in counting problems.

Reconstructing the Subset — From DP Table to Actual Elements

Knowing that a subset exists is half the answer. Often you need the actual elements (e.g., for a budget breakdown or a load-balancing plan). The 2D DP table preserves enough information to reconstruct one valid subset via backtracking.

Backtracking algorithm: 1. Start at dp[n][target]. 2. For i from n down to 1: - If dp[i][target] is true and dp[i-1][target] is also true, the element i was NOT included (the answer came from skipping). Move up without changing target. - If dp[i][target] is true and dp[i-1][target] is false, element i WAS included. Record numbers[i-1], subtract it from target, move up. 3. When target reaches 0, you have the subset.

This works because the recurrence is monotonic — once a sum becomes reachable, it stays reachable for all subsequent rows. So by comparing the current row to the previous, you deduce the decision.

1D version limitation: The space-optimized 1D array does NOT store enough history. If you need reconstruction, you must either: - Keep a second boolean array 'choice[i][s]' that records whether element i was selected to reach sum s — but that uses O(n·W) again. - Use a technique called 'path reconstruction with parent pointers' where you store the last element used to reach each sum. For each sum, record which element (or its index) made dp[sum] become true for the first time. Then you can walk backwards from target to 0. This uses only O(W) extra space (an int array of size W+1).

Here's the parent-pointer reconstruction pattern.

io/thecodeforge/subsetsum/SubsetSumReconstruct.javaJAVA

package io.thecodeforge.subsetsum;

import java.util.*;

public class SubsetSumReconstruct {

    public static void main(String[] args) {
        int[] numbers = {3, 34, 4, 12, 5, 2};
        int target = 9;

        List<Integer> subset = getSubset(numbers, target);
        System.out.println("Subset: " + subset); // [5, 4] or [3, 4, 2]
    }

    /**
     * Returns a list of elements that sum to target, or empty list if impossible.
     * This uses parent-pointer reconstruction which works with any DP variant.
     */
    public static List<Integer> getSubset(int[] numbers, int target) {
        int n = numbers.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        // Fill DP table and record choices
        for (int i = 1; i <= n; i++) {
            int elem = numbers[i - 1];
            for (int s = 1; s <= target; s++) {
                dp[i][s] = dp[i - 1][s];
                if (s >= elem && dp[i - 1][s - elem]) {
                    dp[i][s] = true;
                }
            }
        }

        if (!dp[n][target]) return Collections.emptyList();

        List<Integer> subset = new ArrayList<>();
        int remaining = target;
        for (int i = n; i > 0 && remaining > 0; i--) {
            // If the sum could be achieved without element i, it must have been skipped
            if (dp[i - 1][remaining]) continue;
            // Otherwise it must have been included
            subset.add(numbers[i - 1]);
            remaining -= numbers[i - 1];
        }
        return subset;
    }

    /**
     * Space-optimized version with parent pointer.
     * parent[s] stores the index of the last element that made sum s reachable (or -1 if reachable via empty set).
     */
    public static List<Integer> getSubsetOptimized(int[] numbers, int target) {
        boolean[] dp = new boolean[target + 1];
        int[] parent = new int[target + 1];
        Arrays.fill(parent, -1);
        dp[0] = true;
        parent[0] = -2; // marker for empty set

        for (int i = 0; i < numbers.length; i++) {
            int elem = numbers[i];
            for (int s = target; s >= elem; s--) {
                if (!dp[s] && dp[s - elem]) {
                    dp[s] = true;
                    parent[s] = i; // record which element led to this sum
                }
            }
        }

        if (!dp[target]) return Collections.emptyList();

        List<Integer> subset = new ArrayList<>();
        int s = target;
        while (s > 0) {
            int idx = parent[s];
            if (idx == -1) break; // safety
            subset.add(numbers[idx]);
            s -= numbers[idx];
        }
        return subset;
    }
}

Output

Subset: [5, 4]

🔥Interview Gold: Parent-Pointer Technique

Most candidates know backtracking on the 2D table. The parent-pointer technique is a space-efficient alternative that uses only O(W) extra space. It's a strong signal that you understand the DP's state transitions. Practice reconstructing not just one subset, but all subsets (which requires more advanced DP like storing lists of sums).

📊 Production Insight

In production, you often need the actual subset (e.g., which items to include in a shipment).

The 1D DP without parent pointers cannot reconstruct — switch to 2D or use parent array.

Parent array adds only O(W) memory, which is often acceptable.

🎯 Key Takeaway

Backtracking the 2D table gives the actual subset in O(n) time.

For 1D, use a parent pointer array of size W+1.

Always implement reconstruction if your system needs the 'what', not just the 'whether'.

The Recursive Root Canal — Why O(2ⁿ) Still Matters

Before you write a single DP table, you need to understand the recursion that drives it. Not because you'll ship exponential code — you won't. But because every optimization you're about to see is just a cache slapped on top of this naive explosion.

The recursion is brutally simple: at each element, you branch. Include it and subtract from the target sum. Exclude it and keep the sum unchanged. Two branches per element. That's 2ⁿ leaf nodes. For an array of 30 elements, that's over a billion calls. Your CPU will throw up its hands.

The base cases are your exits: sum == 0 means you found a subset — return true. n == 0 and sum > 0 means you ran out of elements — return false. That's it. The entire problem collapses to a binary decision tree.

Why bother with this when DP exists? Because this is the skeleton. Memoization literally wraps a map around this exact recursion. Tabulation builds the same states in a table. If you can't trace this recursion by hand, you will never understand why DP saves your ass.

SubsetSumRecursive.javaJAVA

// io.thecodeforge — dsa tutorial

public class SubsetSumRecursive {

    public static boolean hasSubsetSum(int[] weights, int n, int target) {
        // Base cases
        if (target == 0) return true;
        if (n == 0) return false;

        // If last element > target, exclude it
        if (weights[n - 1] > target) {
            return hasSubsetSum(weights, n - 1, target);
        }

        // Branch: include or exclude the last element
        boolean include = hasSubsetSum(weights, n - 1, target - weights[n - 1]);
        boolean exclude = hasSubsetSum(weights, n - 1, target);
        return include || exclude;
    }

    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int target = 9;
        System.out.println(hasSubsetSum(arr, arr.length, target));
    }
}

Output

true

⚠ Production Trap:

Never let this code near production. 2ⁿ grows so fast that n=50 would outlive your cloud instance. Use recursion only as a reasoning tool, never a runtime strategy.

🎯 Key Takeaway

Every DP solution is a cached version of the brute-force recursion tree. Master the tree, then add the cache.

Top-Down Memoization — Your First Real Optimization

The recursive approach is honest but stupid. It recomputes the same (n, sum) pairs over and over. Memoization fixes that with one dictionary: a cache keyed by the remaining index and the remaining target sum.

Here's the insight: when you call hasSubsetSum(arr, 3, 5) from two different branches, the answer is always the same. State is deterministic — only the index and remaining sum define the subproblem. Cache it. The first time you compute it, store the result. Every subsequent call is a O(1) lookup.

The time drops from O(2ⁿ) to O(n × sum). For sum=1000 and n=100, that's 100,000 states instead of 1.3e30 calls. The space cost is the cache itself — O(n × sum) in the worst case.

Why choose this over bottom-up? Sometimes you don't know the exact sum bound. Sometimes the recursive formulation maps more naturally to the problem. Memoization gives you the same asymptotic performance as tabulation with less mental overhead when the recursion is already clear. Just don't forget the base cases: they're identical to the naive version.

SubsetSumMemoization.javaJAVA

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SubsetSumMemoization {

    public static boolean hasSubsetSum(int[] weights, int n, int target, Boolean[][] memo) {
        if (target == 0) return true;
        if (n == 0) return false;
        if (memo[n][target] != null) return memo[n][target];

        if (weights[n - 1] > target) {
            memo[n][target] = hasSubsetSum(weights, n - 1, target, memo);
        } else {
            boolean include = hasSubsetSum(weights, n - 1, target - weights[n - 1], memo);
            boolean exclude = hasSubsetSum(weights, n - 1, target, memo);
            memo[n][target] = include || exclude;
        }
        return memo[n][target];
    }

    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int target = 9;
        Boolean[][] cache = new Boolean[arr.length + 1][target + 1];
        System.out.println(hasSubsetSum(arr, arr.length, target, cache));
    }
}

Output

true

💡Senior Shortcut:

Use Boolean[][] for memo — null means uncomputed, true/false are cached results. Primitives can't represent 'not yet computed' without a sentinel value.

🎯 Key Takeaway

State is (index, remaining sum). Cache it. Memoization turns exponential into polynomial without changing the recursive logic.

Bottom-Up Tabulation — When You Want Predictable Performance

Memoization is lazy — it only computes states actually visited. Tabulation is the opposite: you build a complete truth table for all possible states upfront. Every cell dp[i][j] answers: "Can the first i elements sum to j?"

The table is (n+1) × (sum+1). First column j=0 is all true — empty subset sums to zero. First row i=0, j>0 is all false — no elements means no sum. Then you fill: dp[i][j] = dp[i-1][j] (exclude current) OR dp[i-1][j - weights[i-1]] (include it, if j >= weights[i-1]).

Why do this instead of memoization? Predictable memory and runtime. No recursion stack to blow. No hashmap overhead. The loops are tight, cache-friendly, and easy to reason about for code reviews. Plus, when you need to reconstruct the subset, the full table gives you a clear backtracking path.

The downside: you always compute all states, even if most are irrelevant. For sum=10000, that's 10,000 columns. Memory can hurt. That's exactly why the space-optimized 1D version exists — your existing section covers that.

Use tabulation when sum is bounded and small enough to fit in memory. Use memoization when the state space is sparse or the recursion tree is deep.

SubsetSumTabulation.javaJAVA

// io.thecodeforge — dsa tutorial

public class SubsetSumTabulation {

    public static boolean hasSubsetSum(int[] weights, int target) {
        int n = weights.length;
        boolean[][] dp = new boolean[n + 1][target + 1];

        // Sum 0 is always achievable
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                // Exclude current element
                dp[i][j] = dp[i - 1][j];
                // Include if possible
                if (j >= weights[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - weights[i - 1]];
                }
            }
        }
        return dp[n][target];
    }

    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int target = 9;
        System.out.println(hasSubsetSum(arr, target));
    }
}

Output

true

🔥When to Skip Tabulation:

If target sum is > 10⁶, tabulation is dead on arrival. You'll OOM before you fill row 2. Use memoization or the 1D space-optimized version instead.

🎯 Key Takeaway

Tabulation gives predictable O(n × sum) memory and runtime. Always compute the table row by row, column by column — no recursion, no surprises.

● Production incidentPOST-MORTEMseverity: high

Left-to-Right Bug in 1D DP Caused Silent Data Corruption

Symptom

The engine reported 'subset exists' for budgets that were mathematically impossible given the set of item costs. For example, input {5,3} with target 10 returned true, implying 5+5 uses the same item twice.

Assumption

The developer assumed that 1D DP iteration direction is a micro-optimization and that left-to-right also works — 'after all, we're just updating a boolean array'.

Root cause

Left-to-right inner loop reads dp[sum - number] that has already been updated in the same pass — effectively allowing unlimited reuse of the current item. This turns 0/1 Subset Sum into Unbounded Knapsack.

Fix

Changed the inner loop direction from for (int sum = number; sum <= target; sum++) to for (int sum = target; sum >= number; sum--).

Key lesson

Right-to-left iteration in 0/1 knapsack variants is not a style choice — it is the correctness condition.
Always test 1D DP against a brute-force ground truth for small random inputs before deploying.
Add a unit test that explicitly checks that items cannot be reused (e.g., input {3,5}, target 9 must return false).

Production debug guideSymptom → Action table for the most common DP implementation issues4 entries

Symptom · 01

Space-optimized DP returns true for impossible targets (reuses items)

→

Fix

Check inner loop direction. Must be for (sum = target; sum >= number; sum--). Run a test with {3,5} target 9 — should be false.

Symptom · 02

Always returns false regardless of input

→

Fix

Verify dp[0] = true initialisation. Without that seed, no sum propagates. Also check that your 'skip' branch is correctly inherited.

Symptom · 03

ArrayIndexOutOfBoundsException with negative input values

→

Fix

Subset Sum DP assumes non-negative integers. Add input validation: throw or shift all values by -min to make them non-negative.

Symptom · 04

StackOverflowError with memoized recursion on large n

→

Fix

Switch to iterative bottom-up DP (2D or 1D). The recursive version's call stack depth equals n, which can hit JVM limits around 1000 frames.

★ Subset Sum DP Debugging Cheat SheetFive commands that diagnose the most common DP failures in production

Space-optimized DP returns incorrect true for impossible target−

Immediate action

Print the dp array after each outer iteration to see if any element is used multiple times.

Commands

For {3,5}, target 9:
System.out.println(Arrays.toString(dp)); // If dp[6] becomes true before processing 3?

Add assertion:
assert canAchieveTargetOptimized(new int[]{3,5}, 9) == false : "Item reuse detected";

Fix now

Change inner loop to iterate right-to-left: for (int sum = target; sum >= number; sum--)

Always returns false+

Negative input causes crash+

StackOverflowError with recursion+

Subset Sum Approach Comparison

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

⚙ Quick Reference

8 commands from this guide

File	Command / Code	Purpose
SubsetSumMemoized.java	public class SubsetSumMemoized {	Why Brute Force Fails and What Memoization Actually Saves
SubsetSumDP2D.java	public class SubsetSumDP2D {	Building the 2D DP Table
SubsetSumOptimized.java	public class SubsetSumOptimized {	Space-Optimized 1D DP
iothecodeforgesubsetsumSubsetSumEdgeCases.java	public class SubsetSumEdgeCases {	Handling Edge Cases
iothecodeforgesubsetsumSubsetSumReconstruct.java	public class SubsetSumReconstruct {	Reconstructing the Subset
SubsetSumRecursive.java	public class SubsetSumRecursive {	The Recursive Root Canal
SubsetSumMemoization.java	public class SubsetSumMemoization {	Top-Down Memoization
SubsetSumTabulation.java	public class SubsetSumTabulation {	Bottom-Up Tabulation

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.

LEETCODE PRACTICE · 5 PROBLEMS

Practice These on LeetCode

Open LeetCode

#416Medium

Partition Equal Subset Sum

Directly applies subset sum by checking if a subset of array elements can sum to exactly half the total sum using 0/1 knapsack DP.

Solve on LeetCode

#698Medium

Partition to K Equal Sum Subsets

Extends subset sum to multiple partitions, requiring backtracking with pruning to find k disjoint subsets each summing to a target value.

Solve on LeetCode

#1049Medium

Last Stone Weight II

Models the problem as finding a subset sum closest to half the total weight, reducing to the classic subset sum DP formulation.

Solve on LeetCode

#494Medium

Target Sum

Transforms to subset sum by assigning + or - signs, counting the number of ways to achieve a target sum using DP on subset sums.

Solve on LeetCode

#2035Hard

Partition Array Into Two Arrays to Minimize Sum Difference

Requires generating all subset sums for each half of the array and using meet-in-the-middle to find the minimal difference, a classic subset sum optimization.

Solve on LeetCode

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

The Subset Sum Problem is NP-Complete — yet you just gave me an O(n·W) s...

Q02SENIOR

If I asked you to count ALL subsets that sum to the target (not just det...

Q03SENIOR

You've implemented the 1D space-optimized version. Now I want to also re...

Q04SENIOR

How would you solve Subset Sum if the input array can contain negative n...

Q01 of 04SENIOR

The 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?

ANSWER

No contradiction. O(n·W) is pseudo-polynomial: polynomial in the numeric value W, but W is represented in input with log₂(W) bits. If W = 2^50, the algorithm is exponential in input size. NP-Completeness is defined on input length (bits), so the DP is only efficient when W is bounded by a polynomial in n. This is precisely why Subset Sum remains NP-Complete despite having a DP solution.

FAQ · 5 QUESTIONS

Frequently Asked Questions

What is the difference between Subset Sum and the 0/1 Knapsack problem?

Can the Subset Sum Problem handle negative numbers?

Why does Subset Sum remain NP-Complete if dynamic programming solves it in O(n·W) time?

How do I count the number of subsets that sum to a target?

What is the bitset optimization for Subset Sum?

Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Written from production experience, not tutorials.

✓ Verified

production tested

July 19, 2026

last updated

2,466

articles · all by Naren

🔥

That's Dynamic Programming. Mark it forged?

8 min read · try the examples if you haven't