0/1 Knapsack: The First Dynamic Programming Family to Learn

TL;DR: 0/1 knapsack is the dynamic programming family where you walk a list of items and, for each one, decide to include it or skip it, subject to a budget. That single binary choice generates the entire recurrence, and the recurrence generates the table. Partition Equal Subset Sum, Subset Sum, Target Sum, and Last Stone Weight II are the same problem with the budget renamed. Learn this family first, because the other five are variations on the same skeleton, and because one loop direction in the space-optimized version is the difference between this pattern and the next one over.

This is the sixteenth deep dive in our pattern series (the full map lives in the hub), following matrix traversal, and it is the first of two on dynamic programming. If you have not read the six DP patterns overview, start there for the map; this post goes deep on the family that overview lists second, and which I would argue you should learn first. Dynamic programming feels impossible mostly because people meet it as one enormous topic. Meeting it as this one family, where the choice at each step is simply yes or no, is the shortest path to it clicking.

The tell: how to recognize a 0/1 knapsack problem

Suspect this family when there is a collection of items, each usable at most once, and a budget or target:

• "each item can be used once" or "each element belongs to at most one subset"
• a capacity, budget, target sum, or total to hit exactly
• "can you make exactly X from these numbers"
• "partition the array into two subsets with equal sums"
• "the maximum value you can carry within weight W"
• "get as close as possible to half the total"

Then check the counter-tell that sends you one family over: if items may be reused an unlimited number of times, it is unbounded knapsack (Coin Change is the standard example). Stating which of the two you are in, and why, is a real interview signal. They differ by one line of code and interviewers know it.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: for each item you either take it or you do not, and those two branches are independent subproblems on the rest of the list.

That gives the recurrence directly, with no cleverness required:

best(i, remaining) = max(
    best(i + 1, remaining),                              # skip item i
    value[i] + best(i + 1, remaining - weight[i])        # take item i, if it fits
)

Two things are worth noticing. The index only ever moves forward to i + 1, in both branches, which is precisely what enforces "each item at most once". And the state is just two numbers, the position in the list and the budget left, which is why the table is two-dimensional.

Almost every difficulty candidates have with dynamic programming comes from trying to invent the table first. Derive the choice, write it as a recursion, then let the table follow. The recursion is the honest version of your thinking, and it is also what you should say out loud before writing code.

The template, top down

Write the recursion, add memoization, and you have a working solution:

from functools import cache


def knapsack(weights, values, capacity):
    n = len(weights)

    @cache
    def best(i, remaining):
        if i == n or remaining == 0:
            return 0                                      # nothing left to decide
        result = best(i + 1, remaining)                    # skip
        if weights[i] <= remaining:                        # take, only if it fits
            result = max(result, values[i] + best(i + 1, remaining - weights[i]))
        return result

    return best(0, capacity)

This is the version to produce first in an interview. It maps one to one onto the sentence you just said, the base cases are obvious, and @cache turns exponential into polynomial without changing the logic. If you stop here you have a correct, well-explained answer.

The template, bottom up and space-optimized

The follow-up is usually "can you do it with less memory". The 2D table only ever reads the previous row, so it collapses to a single array indexed by the budget. Partition Equal Subset Sum is the cleanest place to show it:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False                                       # odd total cannot split
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True                                           # a sum of 0 is always reachable

    for num in nums:
        for s in range(target, num - 1, -1):               # BACKWARD
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

The backward inner loop is the entire 0/1 constraint, expressed as a loop direction. Iterating downward means every dp[s - num] you read still belongs to the previous item's state, so the current item contributes at most once. Iterate upward instead and you read values this same item already updated, which lets it be used repeatedly. That is not a bug so much as a different problem: forward is exactly how you write unbounded knapsack. One character of direction separates the two families, and it is a favourite thing to probe.

Notice also that the problem was reframed before any DP happened. "Split into two equal halves" became "can a subset reach half the total", which is subset sum. Most problems in this family arrive needing that translation, and doing it out loud is most of the work.

Complexity: O(n × capacity) time and O(capacity) space after the reduction. Say the next part too: this is pseudo-polynomial, not polynomial, because capacity is a numeric value rather than the size of the input. Doubling the capacity doubles the runtime while the input length has not changed. Candidates who volunteer that distinction stand out, because it shows they know what the complexity actually measures.

Want the whole family taught in order? The 0/1 knapsack chapter of Grokking the Coding Interview builds from the raw recursion through memoization, tabulation, and the space-optimized form, with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Subset Sum: can any subset hit exactly this target. The boolean core of the family.
• Partition Equal Subset Sum: subset sum with the target derived as half the total, plus the odd-total early exit.
• Count of Subsets with a Given Sum: change the table from booleans to integers and swap or for +. The structure is untouched, which is a useful thing to notice.
• Target Sum: assign a plus or minus to every number to reach a target. The translation is the problem: if P is the positive group, then P - (total - P) = target, so P = (total + target) / 2, and it becomes counting subsets with that sum. Check that the numerator is non-negative and even before proceeding.
• Last Stone Weight II: smash stones to minimize the remainder. Equivalent to splitting into two groups whose sums are as close as possible, which means getting a subset as near to half the total as you can.
• Ones and Zeroes: two budgets at once, so the table gains a dimension and both inner loops run backward.

The pattern to notice across all six: none of them mention knapsacks. Each one is a translation exercise that lands on the same recurrence.

The three mistakes that sink candidates

1. Running the 1D inner loop forward. The single most common error. It silently converts 0/1 into unbounded, so the code runs fine and returns wrong answers on inputs where reuse changes the result. Backward, every time, and be able to say why.

2. Forgetting dp[0] = True. A sum of zero is reachable by taking nothing. Without that seed the whole table stays false and the function always returns false.

3. Skipping the reframing. Jumping straight to a table before working out what the budget and the items actually are produces a correct algorithm applied to the wrong quantities. Say "the items are the numbers and the budget is half the total" before writing any loops.

Practice ladder

In order, each rung adding one wrinkle.

1. Subset Sum (M): the boolean core, top down first.
2. Partition Equal Subset Sum (M): the halving translation and the odd-total exit.
3. Count of Subsets with a Given Sum (M): booleans become counts.
4. Target Sum (M): the plus and minus translation.
5. Last Stone Weight II (M): minimize the difference.
6. Ones and Zeroes (M): two budgets, two backward loops.
7. Stretch: Partition to K Equal Sum Subsets (H), where the family stops being enough and backtracking takes over.

Then write the tell in your own words ("I should suspect 0/1 knapsack when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One choice (take it or skip it), one recurrence that follows from the choice, one habit worth keeping (derive it top down with memoization before optimizing), one loop direction that enforces single use (backward, and forward is the other family), and one complexity nuance worth volunteering (pseudo-polynomial, because the capacity is a value not a length). Learn this family first and the other five DP patterns stop looking like new material. The full map of where this sits among the other 41 patterns is in the complete pattern guide, and the six DP families are mapped in the dynamic programming guide. Next in the series: Longest Common Subsequence, the family behind Edit Distance.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential DP problems in its 6-week plan.

FAQs

What is the 0/1 knapsack pattern in simple terms? A dynamic programming family where you go through a list of items and decide, for each one, whether to include it, without exceeding a budget. The zero and one refer to how many times an item may be used: never, or exactly once.

What is the difference between 0/1 and unbounded knapsack? Whether an item can be reused. In 0/1 each item is available once, so the recursion always advances to the next index and the space-optimized loop runs backward. In unbounded an item can be taken repeatedly, so the recursion may stay on the same index and the loop runs forward. Coin Change is the standard unbounded problem.

Why must the one-dimensional loop run backward? Because it reads values from the same array it is writing. Going backward guarantees that dp[s - num] still holds the state from before the current item was considered, so the item contributes at most once. Going forward reads values this item already updated, which allows it to be counted multiple times.

Why is O(n × capacity) called pseudo-polynomial? Because capacity is a number in the input, not a measure of the input's size. An input of ten items with a capacity of one million is small to read and large to solve, so the runtime grows with the magnitude of a value rather than with the length of the input.

Should I write the top-down or bottom-up version in an interview? Start top down with memoization. It follows directly from the recurrence you just explained, the base cases are easier to justify, and it is harder to get subtly wrong. Convert to bottom up, and then to the one-dimensional form, if you are asked to reduce memory.