Subset Sum

Subset Sum decides reachability of a target total by building up, from the empty set, the complete set of sums achievable using each prefix of items — a boolean version of 0/1 Knapsack where the only "value" that matters is whether a sum is hit at all, so overlapping include/exclude sub-decisions can be memoized instead of re-explored.

Recognize the pattern

• You're asked does a selection exist hitting an exact target (not the best value) — yes/no or count, not optimize.
• Items are used at most once each (0/1, not unbounded) and have positive weights.
• The target is a fixed number bounded by a reasonable magnitude (pseudo-polynomial hint: if S is small relative to 2^n, DP wins).
• Variants wearing the same mask: Partition Equal Subset Sum, Target Sum (+/- signs), Count of Subsets, Minimum Subset Sum Difference.

Brute force to optimal

Brute force: for each item, recursively branch on include vs exclude, checking if the remaining target reaches 0. Every item doubles the state space regardless of repeated (index, remainingSum) pairs — cost O(2^n) time, O(n) recursion-depth space.

Optimal: notice the recursion state is fully described by (index, remainingSum), and remainingSum only ranges over [0, S]. Cache it: dp[i][s] = can items 0..i-1 sum to s. That collapses the exponential tree into a table of (n+1) x (S+1) cells, each computed in O(1) from cells already known.

Complexity, derived

Recurrence: dp[i][s] = dp[i-1][s] || (s >= item[i-1] && dp[i-1][s-item[i-1]]), base dp[i][0] = true, dp[0][s>0] = false.

• Time: (n+1)*(S+1) cells, O(1) work each → O(n*S).
• Space: naively O(n*S) for the full table; since row i only reads row i-1, a single rolling boolean array of length S+1 suffices → O(S), provided you iterate s from high to low so you don't reuse an already-updated (i.e. current-row) value.

Traced example

Set {1, 2, 3, 7}, target S = 6. Building dp[i][s] row by row (rows = items considered so far, T = reachable):

After including item 3 (value 3), dp[6] = dp_prev[6] (F) OR dp_prev[6-3=3] (T) = T — reached via subset {1, 2, 3}. Item 7 is never needed once 6 is already reachable.

Code

class SubsetSum {
    static boolean canPartition(int[] items, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int item : items) {
            for (int s = target; s >= item; s--) {
                dp[s] = dp[s] || dp[s - item];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 2, 3, 7}, 6)); // true
        System.out.println(canPartition(new int[]{1, 3, 4, 8}, 6)); // false
    }
}

Pitfalls

• Iterating the rolling array low-to-high turns it into an unbounded knapsack (an item can be reused within the same pass) — for 0/1 Subset Sum you must go high-to-low.
• Negative or zero-value items break the [0, S] index range assumption; the classic DP needs positive integers.
• Off-by-one on the target bound: array must be sized target+1, and reading dp[s-item] when s < item is undefined — guard the loop bound (s >= item).
• Confusing this with 0/1 Knapsack-for-value: Subset Sum only needs a boolean table, not an int table of best values — using the wrong one wastes memory and clarity.

When to use / when not

Use the DP when target S is polynomially bounded (interview-sized inputs, or real constraints like currency amounts). It beats brute force's O(2^n) whenever n*S < 2^n, which is almost always for reasonable S.

Avoid it when S is astronomically large (e.g., S ~ 10^15) relative to n — then O(n*S) is worse than exponential-but-small-n brute force, and you instead want meet in the middle: split items into two halves, enumerate all 2^(n/2) subset sums per half, sort one half and binary-search/two-pointer against the other — O(2^(n/2) log(2^(n/2))) time, O(2^(n/2)) space, independent of S. Meet-in-the-middle trades a much smaller time bound for higher constant-factor complexity in implementation and is the right call once n ≤ ~40 but S is huge.

Takeaways

• Subset Sum is 0/1 Knapsack with a boolean payload instead of a value to maximize — same recurrence shape, cheaper table.
• The rolling 1D array with a high-to-low inner loop is the standard space optimization; direction of iteration encodes the "use once" constraint.
• When S dwarfs n, swap DP for meet-in-the-middle — the right tool depends on which of n or S is the binding constraint.

Recall: Why must the inner loop over sums run from high to low when using a single rolling array for 0/1 Subset Sum, and what would break if it ran low to high?

Synthesized from the study guide's DP/Subset Sum notes, cross-checked against the standard 0/1 Knapsack reduction and meet-in-the-middle technique for large-target variants.