Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

The 0/1 knapsack pattern

Lesson · 9 min read · Dynamic programming · Pattern: 0/1 knapsack

Each element is used once or not at all, and the question is about the totals you can reach. A boolean array over sums, filled downwards.

The pattern

Many problems are a 0/1 knapsack in disguise: choose a subset of numbers, each at most once, to reach or approach a target total. The table is indexed by the total; the operator depends on the question (or for "possible", max for "best", sum for "how many").

0/1 knapsack pattern

reach[t]

  1. true if some subset of the numbers seen so far sums to t. reach[0] = true.
  2. For each number x, for t from the target down to x: reach[t] = reach[t] or reach[t − x].

Equal partition is "can half the total be reached?". The smallest difference between two groups is "the reachable sum closest to half the total".

Worked example: subset sum

undefined

Numbers 3, 34, 4, 12, 5, 2; can 9 be reached?

  1. Step 1 / 7
    reach
    T0·1·2·3·4·5·6·7·8·9

    Only 0 is reachable with no numbers.

  2. Step 2 / 7
    reach
    T0·1·2T3·4·5·6·7·8·9

    Allow 3: newly reachable 3.

  3. Step 3 / 7
    reach
    T0·1·2T3·4·5·6·7·8·9

    Allow 34: newly reachable nothing.

  4. Step 4 / 7
    reach
    T0·1·2T3T4·5·6T7·8·9

    Allow 4: newly reachable 4, 7.

  5. Step 5 / 7
    reach
    T0·1·2T3T4·5·6T7·8·9

    Allow 12: newly reachable nothing.

  6. Step 6 / 7
    reach
    T0·1·2T3T4T5·6T7T8T9

    Allow 5: newly reachable 5, 8, 9.

  7. Step 7 / 7
    reach
    T0·1T2T3T4T5T6T7T8T9

    Allow 2: newly reachable 2, 6. reach[9] is true (4 + 5).

How to recognise it

  • Choose a subset; each element once.
  • The constraint or goal is a total that is small enough to index (up to about 10⁴–10⁵).
TimeO(n · target)
SpaceO(target)

The problems in this module: