Autocoder

Knapsack DP Interview Questions

Last updated 2026-11-19

Knapsack problems pick items under a budget, and the pattern appears in many disguises: subset sum, equal partition, target sum, coin change and more. If you can write the 0/1 and unbounded forms from memory, a large share of dynamic programming questions becomes routine.

This page walks through twelve knapsack-style problems, each with Python and Java code, complexity and edge cases. The general method is in dynamic programming interview questions; for sequence alignment problems see longest common subsequence interview questions.

Capacity tabledp[w] over capacities 0..W
0/1 loopCapacity from high to low
Unbounded loopCapacity from low to high
CostO(items * capacity)

The pattern and when to spot it

Suspect knapsack whenever you choose a subset of items that each cost something and the total cost has a limit or target. The state is the remaining budget, and the transition decides whether to use the current item. Variants only change what dp stores: a boolean for feasibility, a count for ways, or a maximum for value.

Two rules cover most mistakes. First, iteration direction: going from high capacity to low forces each item to be used once, going low to high allows reuse. Second, loop nesting for counting: items outside and amounts inside counts combinations, amounts outside and items inside counts ordered sequences. Reductions matter too: equal partition is subset sum for half the total, and target sum becomes subset count for (total + target) / 2.

Notes on complexity

Knapsack DP Interview Questions: questions with worked answers

  1. 1

    0/1 knapsack: maximum value within a weight limit

    medium

    Let dp[w] be the best value with capacity w. For each item, update capacities from high to low: dp[w] = max(dp[w], dp[w - wt] + val). Going downward ensures the item is used at most once, because dp[w - wt] still reflects the state before this item. Time O(n * W), space O(W). Edge cases: capacity 0, an item heavier than the capacity (skipped by the loop bound), zero-weight items (never loop a zero-weight item upward), values that are all zero.

    python
    def knapsack(W, wt, val):
        dp = [0] * (W + 1)
        for w_i, v_i in zip(wt, val):
            for w in range(W, w_i - 1, -1):
                dp[w] = max(dp[w], dp[w - w_i] + v_i)
        return dp[W]
    java
    int knapsack(int W, int[] wt, int[] val) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < wt.length; i++)
            for (int w = W; w >= wt[i]; w--)
                dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        return dp[W];
    }
  2. 2

    Recover which items a 0/1 knapsack picks

    medium

    The one-dimensional array loses information about choices, so keep the full table dp[i][w] for the first i items. Then trace back from dp[n][W]: if dp[i][w] differs from dp[i-1][w], item i-1 was taken, so reduce w by its weight. Collect the items and reverse if order matters. Time O(n * W) time and space, space O(n * W). Edge cases: ties (either choice is optimal), capacity 0 (no items), an item with zero weight and positive value is always taken.

    python
    def knapsack_items(W, wt, val):
        n = len(wt)
        dp = [[0] * (W + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for w in range(W + 1):
                dp[i][w] = dp[i - 1][w]
                if wt[i - 1] <= w:
                    dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
        chosen, w = [], W
        for i in range(n, 0, -1):
            if dp[i][w] != dp[i - 1][w]:
                chosen.append(i - 1)
                w -= wt[i - 1]
        return dp[n][W], chosen[::-1]
    java
    int knapsackItems(int W, int[] wt, int[] val, List<Integer> chosen) {
        int n = wt.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++)
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];
                if (wt[i - 1] <= w)
                    dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
            }
        for (int i = n, w = W; i > 0; i--)
            if (dp[i][w] != dp[i - 1][w]) { chosen.add(0, i - 1); w -= wt[i - 1]; }
        return dp[n][W];
    }
  3. 3

    Subset sum: does a subset reach the target?

    medium

    Use a boolean dp where dp[s] says some subset of the items seen so far sums to s. dp[0] is true. For each number, loop sums downward and set dp[s] |= dp[s - x]. A Python integer used as a bitset (bits |= bits << x) gives a very short alternative. Time O(n * target), space O(target). Edge cases: target 0 (true, empty subset), a number larger than the target, negative numbers (shift by an offset or use a map), empty array.

    python
    def subset_sum(nums, target):
        dp = [True] + [False] * target
        for x in nums:
            for s in range(target, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]
        return dp[target]
    java
    boolean subsetSum(int[] nums, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums)
            for (int s = target; s >= x; s--) dp[s] |= dp[s - x];
        return dp[target];
    }
  4. 4

    Partition into two subsets with equal sum

    medium

    The total must be even, otherwise the answer is no. Then the question is whether a subset sums to total / 2, which is exactly subset sum. Early exit as soon as dp[half] becomes true. Time O(n * total / 2), space O(total / 2). Edge cases: odd total (false), a single element (false unless zero), a number larger than the half makes it impossible, all equal numbers with even count.

    python
    def can_partition(nums):
        total = sum(nums)
        if total % 2:
            return False
        half = total // 2
        dp = [True] + [False] * half
        for x in nums:
            for s in range(half, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]
        return dp[half]
    java
    boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int half = total / 2;
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        for (int x : nums)
            for (int s = half; s >= x; s--) dp[s] |= dp[s - x];
        return dp[half];
    }
  5. 5

    Count subsets with a given sum

    medium

    Change booleans to counts: dp[s] is the number of subsets summing to s, with dp[0] = 1. For each number, loop downward and add dp[s - x]. Zeros double the counts, which is correct because including or excluding a zero gives different subsets. Time O(n * target), space O(target). Edge cases: zeros in the input (each doubles the count), target 0 counts the empty subset, large counts needing long or a modulus.

    python
    def count_subsets(nums, target):
        dp = [1] + [0] * target
        for x in nums:
            for s in range(target, x - 1, -1):
                dp[s] += dp[s - x]
        return dp[target]
    java
    long countSubsets(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int x : nums)
            for (int s = target; s >= x; s--) dp[s] += dp[s - x];
        return dp[target];
    }
  6. 6

    Target sum: ways to assign plus or minus to reach a target

    medium

    Let P be the sum of numbers given a plus and N the sum of those given a minus. Then P - N = target and P + N = total, so P = (total + target) / 2. The question becomes counting subsets with sum P. If total + target is odd or negative, or the target exceeds the total in absolute value, there are zero ways. Time O(n * P), space O(P). Edge cases: odd total + target (0), |target| larger than total (0), zeros which double the count, empty array with target 0.

    python
    def find_target_sum_ways(nums, target):
        total = sum(nums)
        if abs(target) > total or (total + target) % 2:
            return 0
        p = (total + target) // 2
        dp = [1] + [0] * p
        for x in nums:
            for s in range(p, x - 1, -1):
                dp[s] += dp[s - x]
        return dp[p]
    java
    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 s = p; s >= x; s--) dp[s] += dp[s - x];
        return dp[p];
    }
  7. 7

    Minimum difference between two subset sums

    medium

    Find the reachable subset sums up to total / 2. If s is the largest reachable sum not above half, the other subset has total - s, and the difference is total - 2 * s. It is the same table as subset sum. Last stone weight II reduces to this. Time O(n * total / 2), space O(total / 2). Edge cases: single element (difference is the element), all zeros, one huge element dominating the sum.

    python
    def min_subset_diff(nums):
        total = sum(nums)
        half = total // 2
        dp = [True] + [False] * half
        for x in nums:
            for s in range(half, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]
        for s in range(half, -1, -1):
            if dp[s]:
                return total - 2 * s
    java
    int minSubsetDiff(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        int half = total / 2;
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;
        for (int x : nums)
            for (int s = half; s >= x; s--) dp[s] |= dp[s - x];
        for (int s = half; s >= 0; s--) if (dp[s]) return total - 2 * s;
        return total;
    }
  8. 8

    Unbounded knapsack: unlimited copies of each item

    medium

    Same recurrence as 0/1 knapsack, but loop capacities upward so the updated dp[w - wt] may already include the current item, letting it be reused. The direction of the inner loop is the only difference between bounded and unbounded. Time O(n * W), space O(W). Edge cases: capacity 0, a zero-weight positive-value item makes the answer unbounded, items heavier than capacity are skipped.

    python
    def unbounded_knapsack(W, wt, val):
        dp = [0] * (W + 1)
        for w in range(1, W + 1):
            for w_i, v_i in zip(wt, val):
                if w_i <= w:
                    dp[w] = max(dp[w], dp[w - w_i] + v_i)
        return dp[W]
    java
    int unboundedKnapsack(int W, int[] wt, int[] val) {
        int[] dp = new int[W + 1];
        for (int w = 1; w <= W; w++)
            for (int i = 0; i < wt.length; i++)
                if (wt[i] <= w) dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        return dp[W];
    }
  9. 9

    Rod cutting: maximise revenue from cutting a rod

    medium

    price[i-1] is the price of a piece of length i. The best revenue for length n is the max over first cut length i of price[i-1] + best[n - i]. It is an unbounded knapsack where piece length plays the weight. Time O(n^2), space O(n). Edge cases: length 0 (0), a long piece worth less than the sum of shorter pieces, only some lengths priced.

    python
    def rod_cutting(price, n):
        best = [0] * (n + 1)
        for length in range(1, n + 1):
            for i in range(1, min(length, len(price)) + 1):
                best[length] = max(best[length], price[i - 1] + best[length - i])
        return best[n]
    java
    int rodCutting(int[] price, int n) {
        int[] best = new int[n + 1];
        for (int len = 1; len <= n; len++)
            for (int i = 1; i <= Math.min(len, price.length); i++)
                best[len] = Math.max(best[len], price[i - 1] + best[len - i]);
        return best[n];
    }
  10. 10

    Combination sum IV: count ordered sequences that reach a target

    hard

    Here order matters, so (1, 2) and (2, 1) are different. Put the target in the outer loop and the numbers in the inner loop: dp[t] += dp[t - x]. This is the opposite loop order to coin change II, which counts combinations. Time O(target * n), space O(target). Edge cases: target 0 (one way), no number fits, overflow for large targets (the problem usually limits the result to fit in int).

    python
    def combination_sum4(nums, target):
        dp = [1] + [0] * target
        for t in range(1, target + 1):
            for x in nums:
                if x <= t:
                    dp[t] += dp[t - x]
        return dp[target]
    java
    int combinationSum4(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++)
            for (int x : nums) if (x <= t) dp[t] += dp[t - x];
        return (int) dp[target];
    }
  11. 11

    Ones and zeroes: largest subset within a zero and one budget

    hard

    Each binary string costs some zeros and some ones, and the budget is m zeros and n ones. This is a 0/1 knapsack with two capacities. Let dp[i][j] be the most strings using at most i zeros and j ones, and update both dimensions downward for each string. Time O(len(strs) * m * n), space O(m * n). Edge cases: strings that alone exceed the budget, m and n of zero, empty string costing nothing (counted once).

    python
    def find_max_form(strs, m, n):
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            z, o = s.count('0'), s.count('1')
            for i in range(m, z - 1, -1):
                for j in range(n, o - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1)
        return dp[m][n]
    java
    int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int z = 0, o = 0;
            for (char c : s.toCharArray()) if (c == '0') z++; else o++;
            for (int i = m; i >= z; i--)
                for (int j = n; j >= o; j--)
                    dp[i][j] = Math.max(dp[i][j], dp[i - z][j - o] + 1);
        }
        return dp[m][n];
    }
  12. 12

    Bounded knapsack with binary splitting

    hard

    Each item has a limited count c. Treating each copy as a separate item costs O(c) per item. Instead split c into pieces of sizes 1, 2, 4, and a remainder, so every number from 0 to c can be formed by a subset of pieces. Then run the ordinary 0/1 knapsack on the pieces. Time O(W * sum of log c), space O(W). Edge cases: count 0, count 1, the remainder piece when c is not of the form 2^k - 1, large counts where plain expansion would be too slow.

    python
    def bounded_knapsack(W, items):          # items: (weight, value, count)
        pieces = []
        for w, v, c in items:
            k = 1
            while c > 0:
                take = min(k, c)
                pieces.append((w * take, v * take))
                c -= take
                k *= 2
        dp = [0] * (W + 1)
        for pw, pv in pieces:
            for cap in range(W, pw - 1, -1):
                dp[cap] = max(dp[cap], dp[cap - pw] + pv)
        return dp[W]
    java
    int boundedKnapsack(int W, int[][] items) {       // each: {weight, value, count}
        List<int[]> pieces = new ArrayList<>();
        for (int[] it : items) {
            int c = it[2];
            for (int k = 1; c > 0; k *= 2) {
                int take = Math.min(k, c);
                pieces.add(new int[]{it[0] * take, it[1] * take});
                c -= take;
            }
        }
        int[] dp = new int[W + 1];
        for (int[] p : pieces)
            for (int cap = W; cap >= p[0]; cap--)
                dp[cap] = Math.max(dp[cap], dp[cap - p[0]] + p[1]);
        return dp[W];
    }

Frequently asked questions

What is the difference between 0/1 and unbounded knapsack?

In 0/1 knapsack each item can be used at most once, so the capacity loop runs downward. In unbounded knapsack items can repeat, so it runs upward.

Is knapsack solvable in polynomial time?

The DP is O(n * W), which is pseudo-polynomial. The decision version is NP-complete in general, so no polynomial algorithm in the input size is known.

How do I count combinations versus permutations in coin problems?

For combinations put coins in the outer loop. For ordered sequences put the amount in the outer loop. The nesting decides whether (1, 2) and (2, 1) are counted twice.

Do knapsack problems appear in interviews?

Partition equal subset sum, coin change and target sum are very common. See how to crack the DSA coding round for the wider DP expectations.

Related guides

More in DSA Interview Questions

See all in this section