Knapsack variants interview: tell 0/1 from unbounded

In this article

1. Before you start
2. Why interviewers ask this
3. Knapsack variants from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview learning path.

Why interviewers ask this

Knapsack problems test whether a candidate can turn a vague "choose items under a limit" story into a table with a clear meaning for each cell. Public practice sets show the idea in different costumes. Coin Change asks for the fewest coins, Coin Change II asks for the number of combinations, and Partition Equal Subset Sum asks whether an array splits into two equal halves.

A candidate who recognizes the family solves all three with one idea. A candidate who memorized each solution is stuck when the wording changes. A weak answer recites a table without saying why the loops run the way they do. A strong answer names the variant, says what each table cell means, explains the loop direction and states the cost, including the fact that the cost is pseudo-polynomial.

Knapsack variants from first principles

Knapsack variant

A knapsack variant is a version of the problem of choosing items, each with a weight and a value, so that the total weight stays within a capacity. Versions differ in how many copies of an item may be taken, or in what the answer must report: the best value, a minimum count, whether a target is reachable, or the number of ways.

Pseudo-polynomial time

Pseudo-polynomial time is a running time that grows with the numeric value of an input number, such as a capacity, rather than with the number of digits needed to write it. The standard knapsack table has this property, so doubling the capacity doubles the work although the input gets only one bit longer.

Subset sum

Subset sum is the special case of knapsack in which every item's value equals its weight, so the question becomes whether some chosen items add up exactly to a target number, as in splitting an array into two halves of equal sum.

In plain words

Picture packing a bag for a trip. Each object has a weight and a usefulness score. The bag holds only so much weight. You want the most usefulness that fits. The analogy breaks in one place: a real traveller can sometimes take half of an object, but the interview problem lets you take an item whole or not at all. If parts are allowed, a greedy rule on value per weight works. The whole-item version needs dynamic programming.

In one precise sentence, a knapsack variant is a table indexed by capacity in which each item either adds a choice of taking it or does not, and the variants differ only in how often an item may be taken.

Step 1: Name the variant from the item rule

The item rule names the variant. Zero-one knapsack is the variant in which each item is used at most once, so you take it or leave it, as one practitioner write-up puts it: never, or exactly once. Bounded knapsack is the variant in which item i has a copy limit; Bringmann writes it as maximizing value subject to total weight at most the capacity, with each count between zero and the limit. Unbounded knapsack is the variant in which each item has infinitely many copies available.

Then read the question type: best value, fewest items, reachable or not, or number of ways. Input: the problem statement. Output: one variant label and one question type, and the table's cell meaning follows from them.

Step 2: The inner loop direction separates 0/1 from unbounded

The inner loop direction separates 0/1 from unbounded. In the one-array version of the table, cell dp[c] holds the best result for capacity c. Running capacity downward gives zero-one and running it upward gives unbounded, because an upward loop reads cells that the same item has already updated, which lets that item be used repeatedly, while a downward loop reads only cells from before the item was considered (practitioner write-up).

Input: one item and the array. Output: the array after that item. The two versions are the same code with the loop direction flipped, and flipping it by accident silently solves a different problem. That is the common error to avoid: a zero-one answer written with an upward loop returns the unbounded answer.

def best_value(items, capacity, reuse):
    dp = [0] * (capacity + 1)
    for weight, value in items:
        if reuse:   # unbounded: capacity runs upward
            spots = range(weight, capacity + 1)
        else:       # zero-one: capacity runs downward
            spots = range(capacity, weight - 1, -1)
        for c in spots:
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[capacity]

In this code the flag reuse picks the direction. The bounded variant reduces to zero-one by treating each allowed copy as a separate zero-one item. That costs work proportional to the capacity times the sum of the limits, which is slow when the limits are large.

Binary splitting fixes this: split a limit u into bundles of 1, 2, 4 and so on, plus the remainder, and treat each bundle as one zero-one item whose weight and value are the bundle size times the item's. Any count from zero to u is a sum of some bundles. A limit of 13 gives bundles 1, 2, 4 and 6, so 4 items instead of 13,¹ and the cost becomes the capacity times the sum of the logarithms of the limits.

Step 3: Fill the table, one cell per capacity

The table has one cell for each capacity value, and each cell is filled from smaller capacities. Coin Change is the unbounded minimum-count case: the statement says you may assume an infinite number of each kind of coin and asks for -1 when the amount cannot be made. Set dp[0] to zero, fill every other cell with a value larger than the amount to mean "impossible", then for each amount and coin set dp[a] to the smaller of its current value and dp[a - coin] + 1. If the last cell is still the impossible marker, return -1.

Input: coins and an amount. Output: the fewest coins. Partition Equal Subset Sum is zero-one with a yes-or-no cell: if the total is odd the answer is false, and otherwise the target is half the total, and a boolean array with a downward loop marks which sums are reachable. Each step uses only cells already computed.

Step 4: State the cost, which is pseudo-polynomial

The running time is pseudo-polynomial. The standard solution fills one subproblem for each pair of an item and a capacity, so it needs O(nS) subproblems for n items and capacity S; the 0-1 knapsack paper credits this textbook algorithm to Bellman (reference [Bel57], 1957). The one-array version needs space proportional to the capacity.

Input: n and the capacity. Output: the work, n times the capacity. That is not polynomial in the input size, because the capacity is written in digits but costs work in proportion to its value: the MIT notes call it pseudo-polynomial for this reason. Say that sentence aloud in a round; it shows you know why the table is not a proof that hard problems are easy.

1 · Name the variant2 · Pick the loop3 · Fill the table4 · State the costReplay

Step-by-step description

1. The item rule names the variant.
2. Downward is zero-one, upward is unbounded.
3. One cell for each capacity value.
4. The running time is pseudo-polynomial.

• The item rule names the variant.
• Running capacity downward gives zero-one and upward gives unbounded.
• The table has one cell for each capacity value.
• The running time is pseudo-polynomial.

Worked example

Take three illustrative items given as (weight, value): (1, 15), (3, 20) and (4, 30), with capacity 4. With each item usable once, the best value is 35, taking the first two items. With up to three copies of each item the best value is 45, three copies of the first item. With unlimited copies it is 60, four copies of the first item.¹ In short, zero-one reaches 35, three copies reach 45 and unlimited copies reach 60 on the same three items and capacity.¹ If you run the zero-one items with the upward loop by mistake, the code returns 60, the unbounded answer.¹

Text description of the diagram

• The same three items and capacity give best value 35, 45 and 60.
• Zero-one reaches 35, three copies reach 45 and unlimited copies reach 60.

For Coin Change with coins 1, 2 and 5 and amount 11, the answer is 3 coins, 5 plus 5 plus 1, as the problem page states. The filled table, from amount 0 to 11, is 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3.¹ Greedy fails here for other coin sets: with coins 1, 3 and 4 and amount 6, taking the largest coin first gives 4, 1, 1, which is 3 coins, while 3 plus 3 uses 2.¹

The counting rows come from the loop order. Coin Change II asks for the number of combinations, and amount 5 with coins 1, 2 and 5 gives 4 ways. With coins in the outer loop and amounts in the inner loop, each combination is counted once; swapping the loops counts ordered sequences instead, which gives 9 for the same input.¹ The step counts use the published limits of up to 12 coins and an amount of at most 10,000 (LeetCode constraints), giving 120,000 inner steps.¹

For the pseudo-polynomial point, writing a capacity of 1,000,000,000 takes 30 bits, yet with 100 items the table needs 100,000,000,000 steps.¹ Doubling a capacity of 10,000 doubles the steps from 120,000 to 240,000 while the number needed to write it grows from 14 bits to 15.¹

Trade-offs and edge cases

The three variants share one table and differ in how many copies each item may supply, and the choice has costs that candidates are often asked about.

Text description of the diagram

• Partition Equal Subset Sum is a zero-one problem.
• Coin Change is an unbounded problem.

Partition Equal Subset Sum is a zero-one problem, and Coin Change is an unbounded problem. Zero-one is also the family of subset sum, which is the case where each value equals its weight.

• Greedy. Sorting by value per weight and taking items in that order, which costs O(n log n), solves the fractional version, where parts of items may be taken. On whole items it can fail, because leftover capacity goes unused. Largest-coin-first greedy fails on Coin Change too, as the coin example shows.
• Space. A full two-dimensional table for 100 items and capacity 10,000 holds 101 rows (one is the base row) of 10,001 cells, which is 1,010,101 cells, while the one-array version holds 10,001; the saving costs you the ability to read off which items were chosen without extra bookkeeping.¹ The inputs are illustrative.
• Exactly full versus at most. For "at most the capacity", start every cell at zero. For "exactly the capacity", start dp[0] at zero and every other cell at minus infinity (or an impossible marker), so unreachable capacities are never used.
• Two constraints. If each item uses two limited resources, such as weight and volume, the table gets one dimension per limit; for zero-one, both loops run downward.
• Bounded with large limits. Use binary splitting (Step 2) rather than copying each item u times.
• Huge capacity. When the capacity is enormous, the table is too large. The decision version is nondeterministic polynomial time (NP) complete, one of Karp's 21 NP-complete problems, and the optimization version is NP-hard. The table does not contradict this, because it is only pseudo-polynomial. When the item count is small but the capacity is huge, meet-in-the-middle, which splits the items into two halves, runs in O(2^(n/2)·n) time.
• Impossible targets. Keep an explicit marker for "unreachable" and test it before returning, as Coin Change does with -1.
• Early exits. An odd total ends Partition Equal Subset Sum before any table is built.

Not every "choose under a limit" or "sum to k" question is knapsack. Subarray sum equals k asks for contiguous runs and uses prefix sums with a hash map. Longest substring without repeating characters uses a sliding window. Merge intervals is sort-and-sweep. In a real table problem, the fill order must respect dependencies, the same idea as in topological sort.

How to answer it in an interview

The spoken structure: name the variant, define the cell, say the loop direction, state the cost, then test. If the round is in Python, the Python interview questions page covers the language details such code relies on.

Common mistakes

• "I looped capacity upward for Partition Equal Subset Sum." (wrong) That lets a number be used many times. (right) "It is zero-one, so the inner loop runs downward."
• "Coin Change is zero-one knapsack." (wrong) The coins are unlimited. (right) "It is unbounded, so the inner loop runs upward."
• "The table is O(nS), so this is polynomial and the hard problem is solved." (wrong) The capacity is a value, not a length. (right) "It is pseudo-polynomial; the general problem stays NP-hard."
• "Greedy picks the biggest coin each time, so it is optimal." (wrong) Coins 1, 3, 4 and amount 6 break it. (right) "I use the table, because greedy needs a special coin system."
• "I need a two-dimensional table for the partition problem." (wrong) A one-dimensional boolean array with a downward loop is enough. (right) "One array of reachable sums, filled downward."

Follow-up questions

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

In zero-one knapsack each item is used at most once; in unbounded knapsack each item has infinitely many copies. In the one-array table the only code difference is the direction of the capacity loop: downward for zero-one, upward for unbounded.

Is the knapsack dynamic programming solution polynomial time?

No. It is pseudo-polynomial, because the work grows with the numeric value of the capacity rather than with the number of digits needed to write it. The underlying optimization problem is still NP-hard.

How do you handle bounded knapsack with large limits?

Use binary splitting: break each limit u into bundles of 1, 2, 4 and so on plus a remainder, and treat each bundle as one zero-one item. A limit of 13 becomes four items (1, 2, 4, 6) instead of 13, so the work grows with the logarithm of the limits rather than the limits themselves.

Why does greedy fail on Coin Change?

Taking the largest coin first can lock in a bad choice. With coins 1, 3 and 4 and amount 6, greedy uses three coins while two coins of value 3 suffice, so the table is needed.

How is Coin Change II different from Coin Change?

Coin Change asks for the fewest coins and returns -1 when impossible. Coin Change II counts combinations, so each cell adds ways instead of taking a minimum, and coins go in the outer loop so each combination is counted once.

How do you solve Partition Equal Subset Sum?

If the total is odd, return false. Otherwise the target is half the total, and a boolean array with a downward loop marks the reachable sums. See the coding interview path for the neighbouring patterns.

Sources

1. The Knapsack Problem (6.006 recitation notes) — MIT EECS, course 6.006, 26 Oct 2026
2. 0-1 Knapsack in Nearly Quadratic Time (arXiv 2308.04093) — arXiv, 26 Oct 2026
3. Knapsack with Small Items in Near-Quadratic Time (arXiv 2308.03075) — arXiv (Bringmann), 26 Oct 2026
4. Coin Change — LeetCode, 26 Oct 2026
5. Partition Equal Subset Sum — LeetCode, 26 Oct 2026
6. Coin Change II — LeetCode, 26 Oct 2026
7. 0/1 Knapsack: The First Dynamic Programming Family to Learn — Grokking the Coding Interview, 26 Oct 2026