0/1 Knapsack: Take or Skip

In 0/1 knapsack you walk through the items in a fixed order and decide, for each one, take it or skip it. Every item is used at most once. Subset sum, equal partition and target sum all follow this pattern, and so do problems that hide it behind a story, like smashing stones. Once you can see the take-or-skip shape, all of them use the same short template.

The idea#

The state is (i, capacity left) (or (i, sum so far)): which item you're deciding next, and what budget remains. From each state there are two moves.

Skip: solve(i + 1, cap).
Take (if it fits): value[i] + solve(i + 1, cap - weight[i]).

Why does this work? A fixed item order builds each subset exactly once. The future depends only on the budget left, not on which items used it up, so you don't need a used[] list.

How to spot it#

The story rarely says "knapsack", so look for these signals in the question.

"Take or skip each item", "choose a subset", "split into two groups".
Each item can be used once. (Unlimited use is the unbounded variant.)
A numeric budget or target that's small enough to index: sums up to a few thousand, with n up to a couple of hundred.
A story that ends as "some items count plus, the rest count minus". That is a split into two groups.

Template#

Here are the two moves from above as a memoized recursion. Only the combine step changes from problem to problem: max for a best value, or for "is it reachable", + for a count.

solve(i, cap):
    if i == number of items:
        return the base value         # 0, True at target, or 1 way
    result = solve(i + 1, cap)        # skip item i
    if weight[i] <= cap:              # take item i, if it fits
        result = combine(result, value[i] + solve(i + 1, cap - weight[i]))
    return result
memoize solve on (i, cap)
answer: solve(0, full capacity)

There are $n \times C$ states with two moves each, so the cost is $O(nC)$ for budget $C$ .

The 1-D table, right to left#

The same recurrence also works bottom-up, and since each item only looks at the row before it, one row of size C + 1 is enough. The catch is that you must loop the budget right to left.

reachable = [True] + [False] * C      # reachable[s]: some subset sums to s
for each item weight w:
    for s from C down to w:           # right to left: each item once
        if reachable[s - w]:
            reachable[s] = True

The direction matters. Left to right would let reachable[s - w], already updated for this item, feed reachable[s]. That uses the same item twice, which is the unbounded version.

Pitfalls#

Most of these come from losing track of the "each item once" rule.

Iterating capacity left to right in the 1-D table, which silently turns 0/1 into unbounded.
Tracking which items are used in an outer list while caching on other arguments. The key must hold all state (see DP Overview).
Forgetting a parity check when the target is half of a total.
Using this pattern when items can be reused. Check the wording: reuse means unbounded knapsack.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Partition Equal Subset Sum

If the total is odd, the answer is no. Otherwise ask whether a subset reaches total / 2. Build the reachable table and return reachable[half].

Hint: Target Sum

The signs split the numbers into a plus group P and a minus group N. From P - N = target and P + N = total, you get P = (total + target) / 2. Count subsets that sum to P with a count table. If total + target is odd or |target| > total, the answer is 0.

Hint: Last Stone Weight II

Any sequence of smashes ends as the difference between two groups: each stone is added or subtracted once. So find a subset sum s as close to total / 2 as possible; the answer is total - 2 * s. Check: [2, 7, 4, 1, 8, 1] has total 23, best s is 11, answer 1.

Hint: Ones and Zeroes

Each string costs some zeros and some ones, so there are two budgets. The state is (i, zeros_left, ones_left), and taking string i adds 1. Don't loop over "any unused string" with a shared used[] list: the cache key would miss used. Deciding take or skip for string i in order removes the need for it.

Hint: Coin Change (a trap)

Coin Change looks like this pattern, but each coin can be reused. That makes it unbounded knapsack, not 0/1.

Key takeaways#

State = (item index, budget left); transitions = skip or take.
Fixed item order builds each subset once, so no used[] is needed.
In a 1-D table, loop the budget right to left for 0/1 and left to right for unbounded.
"Split into two groups" and "assign + or -" are subset sums in disguise.

Core idea#

Walk the items in a fixed order and decide take or skip for each one. Each item is used at most once. The state is (i, capacity left).

Key points#

Skip: solve(i + 1, cap). Take, if it fits: value[i] + solve(i + 1, cap - weight[i]).
A fixed item order builds each subset exactly once, so no used[] list is needed.
The future depends only on the budget left, not on which items used it.
Spot it: "choose a subset", "split into two groups", and a budget small enough to index.
In a 1-D table, loop the budget right to left for 0/1. Left to right reuses items (unbounded).
Two budgets add a dimension: Ones and Zeroes is (i, zeros_left, ones_left).

Disguises#

Problem	Reduction
Partition Equal Subset Sum	Odd total: no. Else can a subset reach `total / 2`?
Target Sum	Count subsets summing to `P = (total + target) / 2`
Last Stone Weight II	Min-difference partition: `total - 2 * s`, `s` near `total / 2`

Template#

reachable = [True] + [False] * C      # reachable[s]: some subset sums to s
for each item weight w:
    for s from C down to w:           # right to left: each item once
        if reachable[s - w]:
            reachable[s] = True
answer: read reachable at the target, or the best s

Pitfalls#

Looping capacity left to right in the 1-D table. It silently turns 0/1 into unbounded.
Tracking used items in an outer list while caching on other arguments. The cache key then misses part of the state.
Forgetting the parity check in equal partition and target sum. Target Sum is also 0 when |target| > total.
Coin Change allows reuse, so it is unbounded knapsack, not this pattern.

Say it in an interview#

"State is item index and budget left. The choices are skip or take."
Last Stone Weight II: "Any sequence of smashes is the difference of two groups, so this is a partition."