Knapsack DP Patterns: 0/1, Unbounded & Subset Sum Variants

Knapsack is the most reused idea in interview DP. The textbook version (a thief, a bag, items with weights and values) is rarely asked directly. What gets asked is partition equal subset sum, target sum, coin change, last stone weight II, ones and zeroes and perfect squares. Every one of those is a knapsack table with a different operator or loop order, and none of them mentions a knapsack.

This guide builds the pattern from the classic problem, explains the one subtle detail that causes most bugs (the direction of the capacity loop), and then maps the disguised problems onto it. By the end you should be able to look at a new problem and say "0/1, counting, target (total + k)/2" before writing code.

The Knapsack Problem and Why Greedy Fails

You have n items, item i with weight w_i and value v_i, and a bag of capacity W. Choose a subset with total weight ≤ W and maximum total value. Each item is either taken or not; that's the "0/1".

The natural first idea is greedy: sort by value per unit weight and take items while they fit. It fails. Take capacity 50 with items:

Greedy takes A and B (weight 30, value 160), then C doesn't fit. The best choice is B and C (weight 50, value 220). Greedy left 20 units of capacity empty because it committed to A early. That's the signature of a problem that needs DP: a locally good choice can block a globally better combination.

Greedy is optimal for the fractional knapsack, where you may take part of an item: fill by ratio and take a fraction of the last one. Being able to say which version admits greedy, with this counterexample, is a common interview checkpoint, and it's covered alongside other exchange arguments in greedy algorithms problems.

0/1 Knapsack: State, Recurrence and Table

• State: dp[i][c] = maximum value using only the first i items with capacity c.
• Base: dp[0][c] = 0 for all c (no items, no value).
• Transition: for item i (weight w, value v), either skip it, giving dp[i−1][c], or take it if w ≤ c, giving dp[i−1][c−w] + v. Take the max.

The important detail: taking item i reads from row i−1. That's what enforces "at most once": after taking it, only earlier items are available.

Filled table

Weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7:

Trace one cell: row 3, c = 7. Skip the weight-4 item: 5. Take it: dp[2][3] + 5 = 4 + 5 = 9. So 9, which is items of weight 3 and 4. In the last row, taking the weight-5 item at c = 7 gives dp[3][2] + 7 = 8, less than 9, so the answer stays 9.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                          # skip
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)  # take once
    return dp[n][W]

static int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        int w = wt[i - 1], v = val[i - 1];
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];
            if (w <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + v);
        }
    }
    return dp[n][W];
}

Top-down version

If you think more naturally in recursion, write it as "best(i, c) = best value from items i..n−1 with capacity c" and memoise:

from functools import lru_cache

def knapsack_memo(weights, values, W):
    @lru_cache(maxsize=None)
    def best(i, c):
        if i == len(weights):
            return 0
        res = best(i + 1, c)                                   # skip
        if weights[i] <= c:
            res = max(res, values[i] + best(i + 1, c - weights[i]))  # take
        return res
    return best(0, W)

Same O(n·W) states. It only visits reachable (i, c) pairs, which can be fewer than the full table, but recursion depth is n. Both are acceptable in interviews; the conversion between them is explained in recursion for beginners.

Which items were chosen?

Walk back from dp[n][W]: if dp[i][c] ≠ dp[i−1][c], item i was taken, so record it and subtract its weight from c. This requires the 2D table, which is the trade-off of the optimisation below.

The 1D Optimisation and the Loop-Direction Rule

Row i only reads row i−1, so one array of size W + 1 is enough, as long as you're careful about the order you overwrite it.

def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):         # HIGH to LOW
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]

static int knapsack1D(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < wt.length; i++)
        for (int c = W; c >= wt[i]; c--)
            dp[c] = Math.max(dp[c], dp[c - wt[i]] + val[i]);
    return dp[W];
}

Why downward? When we compute dp[c], we need dp[c − w] from before this item was considered (row i−1). Going from high c to low c, dp[c − w] hasn't been touched yet in this pass, so it still holds the old value. Going upward, dp[c − w] might already include this item, and adding it again uses the item twice.

A minimal demonstration with one item (weight 2, value 3) and W = 4:

That "bug" is precisely the unbounded knapsack. So the rule fits in one line: downward = each item once, upward = unlimited copies.

Unbounded Knapsack: Coin Change and Rod Cutting

When each item can be used any number of times, the "take" option reads from the same row: dp[i][c] = max(dp[i−1][c], dp[i][c−w] + v). In one array, that's the upward loop.

def unbounded_knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(w, W + 1):             # LOW to HIGH: reuse allowed
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]

Coin Change (LeetCode 322): minimum coins

Items are coins, "weight" is the coin's value, there's no value to maximise. Instead, minimise the count. Unreachable amounts start at infinity.

def coinChange(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount                 # dp[0] = 0 coins for amount 0
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != INF else -1

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);              // "infinity" that can't overflow on +1
    dp[0] = 0;
    for (int coin : coins)
        for (int a = coin; a <= amount; a++)
            dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

Using amount + 1 as infinity in Java avoids Integer.MAX_VALUE + 1 overflowing to a negative number, a bug that silently produces wrong minimums. Greedy (largest coin first) works for Indian currency denominations but fails for arbitrary ones like [1, 3, 4] with amount 6 (greedy gives 4+1+1, optimal is 3+3). The full walkthrough is in Coin Change explained.

Rod Cutting is unbounded knapsack where piece lengths are weights and prices are values. Perfect Squares (279) is Coin Change with coins 1, 4, 9, 16, ….

Feasible, Count, Optimise: Same Table, Different Operator

Almost every knapsack question asks one of three things about reaching a target. The table and loops stay the same; only the combine operator and the initial values change.

Note the initialisation difference between "capacity at most c" (start everything at 0) and "exactly c" (start at −∞/∞ except dp[0]). Getting that wrong gives answers for unreachable targets.

The Subset Sum Family (All 0/1 Knapsack)

Partition Equal Subset Sum (LeetCode 416)

Can the array be split into two subsets with equal sums? Only if the total is even and some subset sums to total / 2. That's feasibility subset sum.

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for c in range(target, x - 1, -1):     # 0/1: downward
            dp[c] = dp[c] or dp[c - x]
        if dp[target]:
            return True                        # early exit
    return dp[target]

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;
    int target = total / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int x : nums)
        for (int c = target; c >= x; c--)
            dp[c] = dp[c] || dp[c - x];
    return dp[target];
}

A neat Python alternative uses an integer as a bitset: bit c is set if sum c is reachable, and adding item x is bits |= bits << x. Then check (bits >> target) & 1. It's the same DP, done 64 bits at a time by the big-integer arithmetic, and in C++ std::bitset does the same. Worth mentioning as an optimisation, not as your primary answer.

Target Sum (LeetCode 494)

Assign + or − to each number so the expression equals target; count the ways. Let P be the sum of numbers with +, N with −. Then P − N = target and P + N = total, so P = (total + target) / 2. Count subsets summing to P.

def findTargetSumWays(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0                               # impossible
    P = (total + target) // 2
    dp = [1] + [0] * P
    for x in nums:
        for c in range(P, x - 1, -1):
            dp[c] += dp[c - x]
    return dp[P]

public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int x : nums) total += x;
    if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
    int P = (total + target) / 2;
    int[] dp = new int[P + 1];
    dp[0] = 1;
    for (int x : nums)
        for (int c = P; c >= x; c--)
            dp[c] += dp[c - x];
    return dp[P];
}

Zeros in the input are handled correctly: for x = 0 the loop runs c from P down to 0 and does dp[c] += dp[c], doubling each count, which matches the two sign choices for zero. The guard conditions are where people lose points: without the abs(target) > total check, P can be negative and the array allocation fails.

Dry run on nums = [1, 1, 1, 1, 1], target 3: total 5, P = 4. Counting subsets of five 1s that sum to 4 gives C(5, 4) = 5, which matches the five ways to place one minus sign.

Last Stone Weight II (LeetCode 1049)

Smashing stones repeatedly is equivalent to splitting them into two groups and taking the difference. Minimise |S₁ − S₂| = total − 2·S₁ with S₁ ≤ total/2. So find the largest reachable subset sum ≤ total // 2 with feasibility DP, and return total − 2·best. The hard part is the reduction, not the DP; the problem statement never mentions subsets.

Coin Change II vs Combination Sum IV: Loop Order Matters

Both ask "how many ways to make the target from these numbers, with unlimited reuse". They return different answers because they count different things, and the only code difference is which loop is outside.

def change(amount, coins):                 # Coin Change II (518): combinations
    dp = [1] + [0] * amount
    for coin in coins:                     # coins OUTSIDE
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    return dp[amount]

def combinationSum4(nums, target):         # Combination Sum IV (377): permutations
    dp = [1] + [0] * target
    for a in range(1, target + 1):         # amounts OUTSIDE
        for x in nums:
            if x <= a:
                dp[a] += dp[a - x]
    return dp[target]

With coins [1, 2] and target 3: change returns 2 ({1,1,1}, {1,2}) and combinationSum4 returns 3 (1+1+1, 1+2, 2+1).

Why: with coins on the outside, all uses of coin 1 are added before coin 2 is ever considered, so every way is built in non-decreasing coin order, and each multiset is counted exactly once. With amounts on the outside, dp[a] considers every possible last number for every amount, so 1+2 and 2+1 end in different numbers and are counted separately. Being able to explain this, rather than just knowing which loop goes where, is one of the clearest signals of DP understanding an interviewer can get.

Bounded Knapsack, Two-Dimensional Capacity and Huge Weights

Bounded knapsack (each item has k copies)

The naive approach treats each copy as a separate 0/1 item, O(W·Σk). The standard trick is binary splitting: replace an item with k copies by bundles of 1, 2, 4, …, 2^p, and a remainder, so that every count from 0 to k is a sum of some bundles. Then run 0/1 knapsack on the bundles, O(W·Σ log k). A monotonic-queue technique reaches O(n·W), but that's rarely expected outside competitive programming.

Two capacities: Ones and Zeroes (LeetCode 474)

Choose the most binary strings with at most m zeros and n ones in total. Each string is an item with a two-dimensional weight. The state gains a dimension and both loops go downward.

public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m + 1][n + 1];
    for (String s : strs) {
        int zeros = 0, ones = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '0') zeros++;
            else ones++;
        }
        for (int i = m; i >= zeros; i--)          // both capacities downward: 0/1
            for (int j = n; j >= ones; j--)
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
    }
    return dp[m][n];
}

When W is huge: flip the DP

O(n·W) is pseudo-polynomial: it's polynomial in the numeric value W, not in the number of bits needed to write it. With W = 10⁹, the table is impossible. If values are small instead, flip the state: dp[v] = minimum weight needed to reach total value exactly v, and the answer is the largest v with dp[v] ≤ W. That's O(n·Σv). With n ≤ 40 and both large, meet in the middle (enumerate 2²⁰ subsets of each half, sort one side, binary search) is the standard answer. The general 0/1 knapsack decision problem is NP-complete, so no approach is polynomial in every parameter; say this if asked "can we do better than n·W?"

How to Spot Knapsack in Disguise

Run this checklist on any problem that involves choosing from a list:

1. Items: is there a list of things where each is chosen or not (or chosen repeatedly)?
2. Budget or target: do the choices add up to a numeric quantity that's bounded or must hit an exact value? Is that quantity small enough to index an array (roughly ≤ 10⁴–10⁵)?
3. Order irrelevance: does only the chosen set matter, not the sequence? (If order matters, it's a permutation count or a different DP.)
4. Question type: possible? how many? best?

If all four apply, it's knapsack. Then decide 0/1 vs unbounded and pick the operator from the table above.

That last row is the useful counterexample. Word Break involves "pieces adding up to a whole", but the pieces must appear in a specific order, so it's a prefix DP over the string, closer to the problems in DP on strings.

Knapsack in Interviews: Presentation, Pitfalls and Problem List

How to present a knapsack solution

1. Name the reduction out loud: "This is 0/1 knapsack counting subsets that sum to P, where P = (total + target)/2."
2. State the dp meaning and base case: "dp[c] is the number of subsets summing to c; dp[0] = 1 for the empty subset."
3. Write the 2D version first if unsure, then compress. Interviewers prefer a correct 2D answer to a buggy 1D one.
4. Justify the loop direction when you compress.
5. Complexity: O(n·W) time, O(W) space, and mention that it's pseudo-polynomial.

Follow-up questions to prepare

• "Return the chosen items." Keep the 2D table and backtrack.
• "What if W is 10⁹?" DP over value, or meet in the middle for small n.
• "What if items can be split?" Fractional knapsack, greedy by ratio.
• "What if each item has a limited count?" Binary splitting.
• "Can you do it in O(W) space and still reconstruct?" Store, per capacity, the last item that improved it, or use divide and conquer; it's a good discussion point more than an expected implementation.

Problem list

Do the first eight until you can classify each one in a sentence before writing code. The last four stretch the pattern in different directions and are good tests of whether the idea has really clicked. For the wider DP landscape, including where knapsack sits relative to LIS, interval and tree DP, see the dynamic programming interview questions guide and LIS patterns.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.