Split items into two piles of equal weight

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
weights = [1, 5, 11, 5]
reach = 1  # bit t set: total t is reachable
for w in weights:
    reach |= reach << w
half = sum(weights) // 2
print(half, bool(reach >> half & 1))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 11 True

Right: 11 alone matches 1 + 5 + 5.

Each shift adds one weight to every total reached so far, so one integer stands in for the whole table.

Why not the others?
  • B 11 False. Total 11 is reachable with the single item 11.
  • C 22 True. Half of 22 is 11.

30-second answer

If the total is odd, it is impossible. Otherwise ask whether some items add up to half the total. Keep the set of totals reachable so far; for each weight, add it to every reachable total (going from the old set so each item is used once). Stop early when half is reached. O(n × S) time for total S, O(S) memory.

Practise saying it · 45 s. No recording, just a timer

Explain the equal-piles check.

Say your answer out loud, then check which of these points you covered:

  • Odd total: no
  • Reachable totals
  • O(n × S)

Deep dive

This is the subset-total (0/1 knapsack) pattern.

Reachable totals can be a set, a boolean list filled from high to low, or the bits of one Python int.

Pseudo-polynomial: fast when totals are small, slow when weights are huge.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def equal_piles(weights: list[int]) -> bool:
    total = sum(weights)
    if total % 2:
        return False  # an odd total cannot split evenly
    half = total // 2
    reach = {0}  # totals some items add up to
    for w in weights:
        reach |= {t + w for t in reach if t + w <= half}
        if half in reach:
            return True
    return half in reach

Common mistakes

  • Filling a boolean list from low to high, which reuses an item twice.
  • Forgetting the odd-total shortcut.

Senior take & follow-ups

Mention 'pseudo-polynomial' and what it means; interviewers like the precision.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you use a Python int as the table?

    Show hint

    reach |= reach << w adds w to every reachable total at once; test bit half.

  2. What about three equal piles?

    Show hint

    That needs a different search (backtracking with pruning), since two subset totals interact.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.