DP: Knapsack Patterns

0/1 vs unbounded, loop direction, combinations vs permutations, and spotting hidden knapsacks.

The knapsack family is the most common group of DP problems in interviews, and most candidates don't realize how many questions belong to it. "Can these numbers be split into two equal halves?", "How many ways can you reach this target with + and −?", "Fewest perfect squares that sum to n": all of them are knapsack in disguise. Learn to recognize the family and pick the right loop order, and these problems become routine.

This lesson builds on Dynamic Programming.

Recognizing a knapsack problem

You have items (numbers, coins, words), a budget or target (a sum, a capacity, a count), and you choose items to reach, fill or optimize the target. Then ask the two questions that decide the template:

0/1 knapsack: each item at most once

The state is dp[c] = the best result using the items seen so far with capacity c. Loop over the items, and for each item loop over the capacity backwards so that each item is used only once.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target           # dp[s]: can some subset sum to s?
    for x in nums:
        for s in range(target, x - 1, -1):   # backwards: x used at most once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

[!WARNING] Why backwards? If you loop forwards, dp[s - x] may already include item x from this same pass, so x gets used twice. Looping backwards reads only values from before this item was considered. Explaining this one detail clearly is a strong signal.

Unbounded knapsack: reuse allowed

Loop the capacity forwards, so an item can be added again in the same pass.

def change(amount, coins):
    dp = [1] + [0] * amount                  # one way to make 0: use nothing
    for c in coins:                          # coins outer → combinations
        for a in range(c, amount + 1):       # forwards: reuse allowed
            dp[a] += dp[a - c]
    return dp[amount]

Combinations vs. permutations: the loop order

For counting problems, the order of the two loops changes the meaning:

Items outer, amount inner counts combinations. 1+2 and 2+1 are counted once. (*Coin Change II*)
Amount outer, items inner counts permutations. Different orders count separately. (*Combination Sum IV*)

def combination_sum4(nums, target):
    dp = [1] + [0] * target
    for t in range(1, target + 1):           # amount outer → permutations
        for x in nums:
            if x <= t:
                dp[t] += dp[t - x]
    return dp[target]

Reducing a problem to knapsack

The hard part is often seeing the knapsack:

Target sum (assign + or − to each number so they sum to T): the positive group P must satisfy P − (total − P) = T, so P = (total + T) / 2. Count the subsets that sum to P. That's a 0/1 count.
Last stone weight II: split the stones into two groups with the smallest difference. Find the subset sum closest to total / 2.
Perfect squares: the items are 1, 4, 9, …, reuse is allowed, and you want the minimum count. Unbounded min.
Ones and zeroes: a 0/1 knapsack with two capacities (zeros and ones), so the table is 2D: dp[z][o].

Templates at a glance

[!INTERVIEW] Mention the 2D version first If the 1D trick feels shaky, write dp[i][c] (using the first i items, with capacity c) first. It's easier to reason about. Then compress it to 1D and explain why the loop direction changes. Interviewers care more about correct reasoning than about saving memory.

Complexity

O(n × capacity) time and O(capacity) space. This is pseudo-polynomial: fast when the target is small, but impractical when the target is around 10⁹. In that case, look for a different approach, such as meet-in-the-middle or a greedy argument.

[!TIP] Practice Partition Equal Subset Sum · Target Sum · Coin Change · Coin Change II · Combination Sum IV · Perfect Squares · 0/1 Knapsack