Knapsack DP

At a glance

The instinct

Whenever a problem hands you a bag of numbers and a target (a capacity, a sum, an amount), and every item is either used or not, think knapsack. Trying every subset is 2ⁿ, but the target is usually small, so you can ask instead: "for every sum from 0 to target, what is the best I can do using the items seen so far?" The DP dimension is the sum, not the subset.

Then answer two questions: May each item be reused? (0/1 vs unbounded) and What do I store per sum? (true/false, max value, min count, or number of ways).

Recognise it

Not this pattern if...

• The target is huge (around 10⁹) while n is small: use meet-in-the-middle or backtracking.
• You must list every combination: that is backtracking; DP only counts or optimises.
• Items must be contiguous: that is a sliding window or prefix-sum problem.
• Order of the chosen items matters and they must increase: that is LIS.

Memory hack

DP framing: state = dp[c], the best result for capacity/sum c; choice = skip the item or take it (dp[c - w] plus its value); base case = dp[0] (true, 0, or 1 way) and everything else "impossible"; order = items in the outer loop, capacity inside in the direction set by reuse.

Analogy: packing a suitcase while checking a cheat-sheet that says, for every smaller suitcase size, the best packing found so far. Each new item only asks, "if I put this in, what is the best packing for the space that remains?"

Say it out loud in the interview:

1. "What is the capacity, and is it small enough to index an array?"
2. "Can an item be reused? That decides the loop direction."
3. "What do I store per capacity - boolean, max, min, or count - and what is dp[0]?"

How it works

For a 0/1 problem, process items one at a time. After processing item k, dp[c] answers the question using only the first k items. Iterating capacity downward guarantees each read of dp[c - w] refers to the previous item layer, so the current item is never counted twice.

Trace for Partition Equal Subset Sum on [1, 5, 11, 5]: total 22, so target 11. Reachable sums after each item:

The answer is true: {11} versus {1, 5, 5}. Had you looped upward, the first 5 would already have produced 10 by stacking on the 5 it had just created in the same pass - using one item twice. Harmless here by luck, wrong in general.

Java template

import java.util.*;

class Knapsack {
    // 0/1 feasibility: can some subset sum to target? (each item at most once)
    static boolean subsetSum(int[] nums, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;                                 // empty subset
        for (int x : nums)
            for (int c = target; c >= x; c--)         // DOWNWARD: item used once
                dp[c] = dp[c] || dp[c - x];
        return dp[target];
    }

    // Unbounded minimum count: fewest items (reusable) summing exactly to target, or -1.
    static int minItems(int[] items, int target) {
        int INF = target + 1;                         // larger than any real answer
        int[] dp = new int[target + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int w : items)
            for (int c = w; c <= target; c++)         // UPWARD: item reusable
                dp[c] = Math.min(dp[c], dp[c - w] + 1);
        return dp[target] >= INF ? -1 : dp[target];
    }

    // Counting. reusable=false -> 0/1 subsets; reusable=true -> combinations (order ignored).
    static int countWays(int[] items, int target, boolean reusable) {
        int[] dp = new int[target + 1];
        dp[0] = 1;                                    // one way to make 0: take nothing
        for (int w : items) {
            if (reusable) for (int c = w; c <= target; c++) dp[c] += dp[c - w];
            else          for (int c = target; c >= w; c--) dp[c] += dp[c - w];
        }
        return dp[target];
    }

    // Ordered counting (permutations): amount outside, items inside.
    static int countOrdered(int[] items, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int c = 1; c <= target; c++)
            for (int w : items)
                if (w <= c) dp[c] += dp[c - w];
        return dp[target];
    }
}

Complexity

• Time: O(n × T), where n is the number of items and T the target. This is pseudo-polynomial: fast when T is small, hopeless when T is around 10⁹.
• Space: O(T) with the 1-D rolling array; O(n × T) if you keep the full 2-D table (needed only to reconstruct which items were chosen).
• Perfect Squares uses √n "coins", so it runs in O(n√n).

Variations

• Subset sum / equal partition: Partition Equal Subset Sum - boolean 0/1 over total/2; bail out early if the total is odd.
• Sign assignment → subset count: Target Sum - transform to counting subsets with sum (total + target) / 2; reject odd or negative values.
• Closest split: Last Stone Weight II - find the largest reachable sum ≤ total/2; answer is total - 2 × that.
• Unbounded min count: Coin Change and Perfect Squares - min(dp[c], dp[c - w] + 1) with an "infinity" sentinel.
• Unbounded combinations: Coin Change II - coins outer, amount inner, upward.
• Ordered combinations: Combination Sum IV - amount outer, items inner.
• Two-capacity knapsack: Ones and Zeroes - a 2-D dp over (zeros, ones), both loops downward.

Common mistakes

• Swapping the loop nesting for counting. Items-outer counts combinations; amount-outer counts permutations. Coin Change II and Combination Sum IV differ only here.
• Bad sentinel. Using Integer.MAX_VALUE as infinity and then adding 1 overflows; use target + 1 or check before adding.
• Wrong base case. Counting needs dp[0] = 1, min-count needs dp[0] = 0 with the rest at infinity, feasibility needs dp[0] = true.
• Skipping the transform checks in Target Sum: if (total + target) is odd or |target| > total, the answer is 0.
• Ignoring zeros in counting problems. Each 0 can be in or out, doubling the ways; keep the loop bound c >= w so c = 0 is processed rather than "optimising" zeros away.

All practice problems

7 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.