Subset Sum

Split a restaurant bill so that one group pays an exact amount. Choose receipts that sum to a figure for the accountant. Pick coins from your pocket that total exactly a price. Each is the same tiny puzzle: from a set of numbers, is there a subset that adds up to an exact target?

That's Subset Sum, perhaps the most stripped-down of all the hard problems. No weights and values like knapsack, no graph, no logic — just numbers and a target. And yet, hidden inside that plainness is genuine, NP-complete difficulty.

Checking a proposed answer is instant; finding one can mean sifting through an exponential number of subsets.

Try it. Click numbers to add them to your selection; your running total updates instantly. Can you hit the target exactly?

<p class="hint">{{hint}}</p>
<div class="target">{{target_label}} <b id="target">15</b></div>
<div id="nums" class="nums"></div>
<div class="sumline">{{sum_label}} <b id="sum">0</b> <span id="match"></span></div>
<div class="bar-btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.target { font-size: 1.05rem; margin: .3rem 0; }
.target b { font-size: 1.4rem; color: #457b9d; }
.nums { display: flex; flex-wrap: wrap; gap: .5rem; margin: .5rem 0; }
.num { width: 52px; height: 52px; border-radius: 10px; border: 2px solid #bbb; background: #fff; cursor: pointer; font: 700 18px ui-monospace, monospace; color: #333; transition: all .1s; }
.num.sel { background: #457b9d; color: #fff; border-color: #457b9d; transform: translateY(-2px); }
.sumline { font-size: 1rem; margin: .4rem 0; font-weight: 600; }
#match.hit { color: #0a7d33; }
#match.miss { color: #888; font-weight: 500; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Notice how effortless it is to check a selection — you just read the sum. Finding one is the hard part: press Find a subset to let the computer search. For a handful of numbers it's instant, but the number of possible subsets doubles with every number you add.

How hard is subset sum?

• Checking is trivial: add the chosen numbers and compare to the target.
• Brute force tries all $2^{n}$ subsets — hopeless beyond a few dozen numbers.
• It's NP-complete, one of Karp's original 21. It's the bare skeleton beneath knapsack and coin change.
• But there's a clever escape. A dynamic program decides it in O(n × target) time — pseudo-polynomial: fast when the target is small, but ballooning when the numbers are huge. And meet-in-the-middle cuts brute force to about $2^{n/2}$.

So subset sum is the minimal embodiment of a recurring lesson: trivial to state, easy to check, and exactly as hard to solve as the whole NP-complete family — see P vs NP.

Whenever the question is "do some of these add up to exactly that?", subset sum is at the core:

• Accounting and auditing: matching transactions to a known total.
• Budgets and allocation: spending an exact amount across line items.
• Cryptography: early public-key systems (Merkle–Hellman) were built directly on subset sum's hardness — and famously broken.
• Fair division: splitting assets into equal-value shares (the partition problem).
• Scheduling and loading: hitting an exact capacity with a chosen set of items.

It's the common ancestor of knapsack, coin change and partition — learn subset sum and you've met the heart of them all.

Subset sum is hardness with nothing to hide behind. Strip away weights, graphs and logic, and you're left with the barest question — do some of these numbers add up to that one? — and it is still NP-complete. Checking stays instant; finding can explode.

That purity is exactly why it matters. Subset sum is the seed from which knapsack, coin change and partition grow, and a crisp reminder that the limits of algorithms aren't about complicated inputs — they're woven into the simplest questions we can ask.