Introduction

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.

Hit the Target

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

<p class="hint">Click numbers to add them to your selection. Can you find a subset that adds up to the target <b>exactly</b>? Checking is instant — finding is the hard part.</p>
<div class="target">Target: <b id="target">15</b></div>
<div id="nums" class="nums"></div>
<div class="sumline">Your sum: <b id="sum">0</b> <span id="match"></span></div>
<div class="bar-btns">
  <button id="find" type="button">Find a subset</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Subset Sum: is there a subset adding up to the target exactly? Checking a
// selection is one addition pass; finding one means searching up to 2^n subsets.
const NUMS = [3, 7, 1, 8, 4, 6];
const TARGET = 15;
const sel = new Set();

function render() {
  const box = document.getElementById('nums'); box.innerHTML = '';
  NUMS.forEach((v, i) => {
    const b = document.createElement('button');
    b.className = 'num' + (sel.has(i) ? ' sel' : '');
    b.textContent = v;
    b.addEventListener('click', () => { sel.has(i) ? sel.delete(i) : sel.add(i); render(); });
    box.appendChild(b);
  });
  let s = 0; sel.forEach(i => s += NUMS[i]);
  document.getElementById('sum').textContent = s;
  const m = document.getElementById('match');
  if (sel.size && s === TARGET) { m.textContent = '= target ✓'; m.className = 'hit'; }
  else if (sel.size) { m.textContent = fmt('(need %TARGET%)', { TARGET: TARGET }); m.className = 'miss'; }
  else { m.textContent = ''; m.className = ''; }
}

function find() {
  let steps = 0, found = null;
  for (let mask = 1; mask < (1 << NUMS.length); mask++) {
    steps++;
    let s = 0; for (let i = 0; i < NUMS.length; i++) if (mask & (1 << i)) s += NUMS[i];
    if (s === TARGET) { found = mask; break; }
  }
  sel.clear();
  if (found !== null) for (let i = 0; i < NUMS.length; i++) if (found & (1 << i)) sel.add(i);
  render();
  console.log(found !== null ? fmt('Found a subset after checking %steps% of %v%.', { steps: steps, v: 1 << NUMS.length }) : 'No subset hits the target.');
}

document.getElementById('find').addEventListener('click', find);
document.getElementById('reset').addEventListener('click', () => { sel.clear(); render(); });
render();
Result
Console

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.

The Real Complexity

How hard is subset sum?

  • Checking is trivial: add the chosen numbers and compare to the target.
  • Brute force tries all 2n2^{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 2n/22^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/subset-sum/Content licensed under CC BY-NC 4.0.