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 table | dp[w] over capacities 0..W |
|---|---|
| 0/1 loop | Capacity from high to low |
| Unbounded loop | Capacity from low to high |
| Cost | O(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
- The runtime O(n * W) is pseudo-polynomial: it depends on the numeric value of W, not just on the input length, so it is exponential in the number of bits.
- For large weights but small values, swap the roles and index the table by value instead.
- Fractional knapsack, where items can be split, is solved greedily by value per weight, not by DP.
- Reconstructing the chosen items needs the two-dimensional table, or a record of choices.
Knapsack DP Interview Questions: questions with worked answers
1 0/1 knapsack: maximum value within a weight limit
mediumLet 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.
pythondef 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]javaint 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 Recover which items a 0/1 knapsack picks
mediumThe 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.
pythondef 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]javaint 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 Subset sum: does a subset reach the target?
mediumUse 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.
pythondef 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]javaboolean 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 Partition into two subsets with equal sum
mediumThe 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.
pythondef 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]javaboolean 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 Count subsets with a given sum
mediumChange 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.
pythondef 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]javalong 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 Target sum: ways to assign plus or minus to reach a target
mediumLet 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.
pythondef 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]javaint 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 Minimum difference between two subset sums
mediumFind 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.
pythondef 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 * sjavaint 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 Unbounded knapsack: unlimited copies of each item
mediumSame 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.
pythondef 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]javaint 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 Rod cutting: maximise revenue from cutting a rod
mediumprice[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.
pythondef 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]javaint 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 Combination sum IV: count ordered sequences that reach a target
hardHere 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).
pythondef 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]javaint 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 Ones and zeroes: largest subset within a zero and one budget
hardEach 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).
pythondef 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]javaint 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 Bounded knapsack with binary splitting
hardEach 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.
pythondef 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]javaint 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
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions