Knapsack DP

Problem

You have a collection of items (numbers, coins, dictionary words) and a target (a sum, an amount, a string length). The question is whether the target is reachable, how cheaply, or in how many ways. Trying every subset is exponential. The way out is to notice that only the total so far matters, not which items made it, so you track a table indexed by totals from 0 to the target.

Intuition

Imagine a row of boxes labelled 0 up to the target, each one lit if that exact total is possible. Start with only box 0 lit (the empty selection). Each new number lets you move from any lit box up by that number, lighting the box you land on. When the numbers are used up, you just check whether the target box is lit. You never need to remember which numbers lit a box, because anything that completes the sum from there looks the same.

The only real choice is whether an item may be used once or many times. If each number can be used once, you process numbers one at a time and each can only act on the boxes that were lit before it. If a coin can be reused, the new box it lights may immediately be used by the same coin again. That single difference decides the direction of the inner loop, and it is where most knapsack bugs live.

Each row is the set of lit boxes after one more number. Green boxes are reachable; the blue box is the target. The diagram scrolls sideways on a narrow screen.

Mechanics

0/1: each item once

Let can[s] say whether sum s is reachable. For each number v, set can[s] = can[s] or can[s - v]. To use v at most once, the right-hand side must read the table as it was before v. Updating a one-dimensional array from the high end down to v guarantees that: when you write can[s], the entry can[s - v] is lower and has not been updated yet. Going upward would let v feed itself and turn the problem into the unbounded one.

Unbounded: items reused

For coins with unlimited supply, fewest[a] = 1 + min(fewest[a - c]) over every coin c not above a, with fewest[0] = 0. The last coin used could be any denomination, so the table takes the best. Here an upward inner loop is correct, because fewest[a - c] may already include another copy of c.

Greedy fails here. With coins 1, 4, 5 and amount 13, largest-first uses 5 coins (5 + 5 + 1 + 1 + 1), while the table finds 3.

Bar height is the number of coins. The blue bar is the answer. Amount 4 is one coin because 4 is itself a denomination, which is why the greedy choice of 5 first goes wrong at 13.

Counting: the loop order decides what is counted

For the number of ways, the update is a sum: ways[a] += ways[a - c]. With denominations in the outer loop and amounts inside, each coin is introduced once and the order inside a selection is fixed, so 1, 2, 5 making 7 counts 6 combinations. Swap the loops (amounts outside, coins inside) and every amount tries every last coin, so 1+2+... and 2+1+... count separately: 26 ordered sequences for the same coins.

Strings: the table runs over lengths

For splitting a string into dictionary words, reach[i] is true when the first i characters split. It holds if some earlier position j has reach[j] true and text[j:i] is a word. The "items" are words and the "amount" is the length, which is why the problem is a knapsack in disguise.

The cell under each gap says whether the prefix ending there splits. Only the ends of "apple" and "pen" are true.

Invariant

After processing the first k items, the table holds the exact answer for every total using only those k items (and, for the 0/1 case, each at most once). Induction on k: an optimal selection either leaves item k out, covered by the previous table, or includes it, in which case the rest is an optimal selection of the first k - 1 items for the smaller total. The table is a bounded set of such sub-answers, which is what makes the cost pseudo-polynomial.

Worked example

Partition (0/1 reachability). The numbers are 3, 1, 5, 9, 12, total 30, so each half must be 15. The reachable sums after each number are in the diagram above; the final row contains 15, so a split exists.

Coin change. For coins 1, 4, 5, the table of fewest coins for amounts 0 to 13 is 0, 1, 2, 3, 1, 1, 2, 3, 2, 2, 2, 3, 3, 3, so 13 needs 3 coins. Largest-first would take 5 + 5 + 1 + 1 + 1, which is 5.

Counting. For coins 1, 2, 5 and amount 7, the table of combinations is 1, 1, 2, 2, 3, 4, 5, 6, giving 6. The ordered version is 1, 1, 2, 3, 5, 9, 15, 26, giving 26.

Word break. For "applepen" and words apple, pen, the reachable prefix lengths are 0, 5, 8, so the string splits as apple + pen.

Target sum. With 1, 1, 2, 3, 1 and target 2, numbers given a plus must sum to (8 + 2) / 2 = 5. The table of subset counts is 1, 3, 4, 5, 6, 5, so there are 5 sign assignments. If 8 plus the target is odd, or the target is bigger than the total, the answer is 0.

Implementation

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    can = [True] + [False] * target
    for value in nums:
        for s in range(target, value - 1, -1):    # downward: each number once
            can[s] = can[s] or can[s - value]
    return can[target]


def coin_change(coins, amount):
    inf = amount + 1
    fewest = [0] + [inf] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                fewest[a] = min(fewest[a], fewest[a - c] + 1)
    return -1 if fewest[amount] == inf else fewest[amount]


def word_break(s, words):
    vocabulary = set(words)
    reach = [True] + [False] * len(s)
    for end in range(1, len(s) + 1):
        reach[end] = any(reach[start] and s[start:end] in vocabulary
                         for start in range(end))
    return reach[-1]

Variations and edge cases

def coin_change_ways(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:                       # coins outside: combinations
        for a in range(c, amount + 1):    # upward: unlimited copies
            ways[a] += ways[a - c]
    return ways[amount]


def combination_sum_ordered(nums, target):
    ways = [1] + [0] * target
    for a in range(1, target + 1):        # amounts outside: ordered
        for v in nums:
            if v <= a:
                ways[a] += ways[a - v]
    return ways[target]


def find_target_sum_ways(nums, target):
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    goal = (total + target) // 2
    ways = [1] + [0] * goal
    for v in nums:
        for s in range(goal, v - 1, -1):
            ways[s] += ways[s - v]
    return ways[goal]


def can_partition_bits(nums):
    total = sum(nums)
    if total % 2:
        return False
    bits = 1
    for v in nums:
        bits |= bits << v                # every reachable sum in one integer
    return bits >> (total // 2) & 1 == 1

• Direction of the inner loop. Downward for use-once, upward for reuse. Reversing either silently solves a different problem.
• Unreachable amounts. Fill with a sentinel larger than any real answer (amount + 1), not float("inf") arithmetic you forget to test, and map it to -1 at the end.
• Zero amount. There is exactly one way (take nothing) and zero coins are needed; seed [0] or [1] accordingly.
• Zeros in the number list. A zero doubles the count of target-sum assignments, since + 0 and - 0 are both valid. The table handles this only if the inner loop reaches 0, so check it.
• Negative targets. Take the absolute value; the signs mirror.
• Words longer than the string. Skip them, or cap the lookback to the longest word, for a faster word break.

Complexity and tradeoffs

• Time: O(n × T) for n items and target T. Word break is O(L × W) with a set of words and a lookback limited to the longest word, otherwise O(L²) substring checks.
• Space: O(T) with a single array; the two-dimensional version (items by totals) is O(n × T) and only needed to recover which items were used.
• Pseudo-polynomial. T is a value, not an input length. If the target is a billion, the table is unusable and the problem is NP-hard in general. Interview constraints keep T small on purpose.
• Baseline. Trying all subsets costs 2ⁿ. Meet-in-the-middle halves the exponent when n is about 40 and T is huge.
• When it fails. Greedy works only for special denominations (like US coins), so use the table when in doubt. If the items have two budgets (weight and volume), the table gains a dimension. If you need the items and not just the count, keep the table and walk back, or keep parent pointers.

Problems

Partition Equal Subset Sum and Last Stone Weight II are 0/1 reachability. Target Sum reduces to counting subsets. Coin Change, Perfect Squares and the ordered Combination Sum IV are unbounded versions with different combining rules, and Coin Change II is the combination count. Word Break and Extra Characters in a String run the same table over string length. Maximum Profit in Job Scheduling is a take-or-skip over jobs ordered by end time.

Medium

• 139. Word Break Blind 75 Grind 169 NeetCode 150 NeetCode 250
  A prefix is breakable if some dictionary word ends it and the part before that word is itself breakable.
• 279. Perfect Squares NeetCode 250
  Treat every perfect square as a coin with unlimited supply and find the fewest coins that reach n.
• 322. Coin Change Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The fewest coins for amount a is one plus the fewest coins for a minus some coin, solved for every amount up to the target.
• 377. Combination Sum IV Grind 169 NeetCode 250
  Count ordered sequences by looping over the target amount outside and the numbers inside, the reverse of counting unordered combinations.
• 416. Partition Equal Subset Sum Grind 169 NeetCode 150 NeetCode 250
  Ask whether some subset reaches half the total, a 0/1 knapsack where the set of reachable sums grows one number at a time.
• 494. Target Sum NeetCode 150 NeetCode 250
  Assigning signs splits the numbers into a plus set and a minus set, so the task becomes counting subsets with a fixed sum.
• 518. Coin Change II NeetCode 150 NeetCode 250
  Loop over coins outside and amounts inside, so each combination is counted once regardless of order.
• 1049. Last Stone Weight II NeetCode 250
  Smashing splits the stones into two groups, so find the subset sum closest to half the total.
• 2707. Extra Characters in a String NeetCode 250
  The best result for a suffix is to skip its first character as an extra or to match any dictionary word starting there, with a trie finding words.

Hard

• 1235. Maximum Profit in Job Scheduling Grind 169
  Sort jobs by end time, and the best profit by job i is the better of skipping it or taking it plus the best before its start, found by binary search.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 140. Word Break II Hard

Connections

Knapsack is linear DP with a second axis. The same take-or-skip structure appears in subsets and permutations, where backtracking enumerates what the table counts. Word Break II is the enumeration partner of Word Break: the table prunes, and a backtracking pass lists the splits. Two-string DP and grid DP use the same idea with two indices instead of an item index and a total.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14 (dynamic programming), and the subset-sum discussion in chapter 34 (NP-completeness).
• Skiena, The Algorithm Design Manual, sections 10.5 and 10.8 (the knapsack problem).
• Sedgewick and Wayne, Algorithms, section 4.4 (acyclic shortest paths): coin change is a shortest path over the amounts 0 to the target, each coin an edge.
• Bellman, Dynamic Programming, Princeton University Press, 1957.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.