Given a set of numbers and a target, does some subset of them add up to exactly the target? Not
which items to sort or which cells to fill — which of 2n possible subsets,
if any, hits one exact number. Like N-Queens,
Sudoku, Graph
Coloring, Hamiltonian Path/Cycle, and
Word Search, there's no formula and no greedy rule that
always works — the same backtracking discipline applies: decide on one item at a time, and the
instant a partial choice can't possibly lead anywhere valid, abandon it. What's different here is
why a choice gets abandoned. Every earlier backtracking entry on this site rejects a
candidate because of a structural conflict — two queens sharing a diagonal, a letter that doesn't
match the next character in the word. This page's two rejection reasons are purely numeric:
a running sum that's already overshot the target, or a remaining budget too small to ever reach it
— checked by comparing totals, not positions.
Five fixed numbers — 3, 7, 4, 6, 2 — and a target of 9, not
user-editable, same convention as this site's other fixed-content interactive demos. The search
considers items in that order. At each item it first tries including it (skipped
outright if that would push the running sum past the target — an immediate reject, no recursive
call at all), then tries excluding it. Before either is tried, the search checks
whether the sum of every item from here to the end could even reach the target if all of them were
included — if not, the whole branch is a dead end and gets pruned without trying
anything further. The moment the running sum hits the target exactly, that combination is recorded
as a solution and the search backs out immediately — every remaining item is positive, so including
even one more could only push the sum past the target, never keep it there.
Checking every subset of these 5 items outright means checking 25 =
32 possible sums. The backtracking search finds all 3 solutions —
{3, 6}, {7, 2}, and {3, 4, 2} — after only
20 recursive calls, computed directly from the demo's own reference
implementation below, not estimated. Two pruning rules do the work: 5 immediate
rejects, where the next item alone would already overshoot the target, and 3
remaining-budget prunes, where even taking every item left on the list couldn't reach the target —
both catch a doomed branch before it's ever explored further, the same principle N-Queens' conflict
check uses, just measured in running totals instead of board positions. The remaining-budget check
matters even when the running sum is well under the target: excluding a large early item can leave
too little total value in everything that's left, and there's no point trying every combination of
what remains once that's already certain.
function subsetSums(items, target) {
const n = items.length;
// suffix[i] = sum of items[i..n-1], the most this branch could ever add from here on
const suffix = new Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + items[i];
const solutions = [];
const chosen = [];
function explore(i, sum) {
if (sum === target) {
solutions.push(chosen.slice());
return; // every remaining item is positive: including more can only overshoot
}
if (i === n) return; // ran out of items on this path
if (sum + suffix[i] < target) return; // even every remaining item can't reach target
if (sum + items[i] <= target) {
chosen.push(items[i]);
explore(i + 1, sum + items[i]);
chosen.pop(); // backtrack: undo the inclusion
}
explore(i + 1, sum); // try excluding item i too
}
explore(0, 0);
return solutions;
}Skipping the early return the moment sum === target double-counts a
solution. It looks like harmless extra work — the recursion would just keep excluding
everything left and arrive at the same total again — but "arrive at the same total again" is
exactly the bug: the identical chosen set gets pushed to solutions more than once.
Checked directly against this page's own data with the early return removed: the
search reports 4 solutions instead of the true 3, because
{3, 6} — found after item 4 (value 6) — gets recorded a
second time when the search continues past it, excludes the last item, and re-checks the same
running sum against the target at the end of the array. The number of distinct subsets is never
ambiguous; a recursion that doesn't stop the moment it finds one can still report the wrong count.
Both pruning rules — the early stop and the remaining-budget check — quietly assume
every item is positive. Neither is true once negative numbers are allowed. Checked with a
throwaway script, not reproducible in this page's demo (which only ever uses positive numbers):
for items = [9, -3, 3] and target = 9, the early-stop version finds only
{9}, while a brute-force check of all 8 subsets finds two solutions,
{9} and {9, -3, 3} — a real solution silently missed, not just
slower. With negative items in play, hitting the target exactly is no longer proof that going
deeper is pointless, and a suffix sum is no longer the true upper bound on what a branch could
still add.
Time: O(2n) in the worst case — pruning cuts the
constant factor, sometimes dramatically (see the attempt counts above), but doesn't change the
underlying order: a target exactly one more than the sum of every item still forces the search to
rule out every single subset before concluding none works, since no prefix sum can end early and
no suffix sum can trigger a prune until the very last item. Space: O(n)
for the chosen array and the recursion stack, since only the current partial subset is
ever held in memory — the search never materializes all 2n candidates at
once.
The same extend/reject/backtrack shape underlies every other Backtracking entry on this site; what's specific to this page is deciding what to reject with arithmetic instead of a structural rule. A related but different question — not whether some subset hits a target sum exactly, but which subset maximizes total value under a weight cap — is 0/1 Knapsack, solved by filling a table bottom-up rather than searching and backtracking. See Choosing a Backtracking Strategy for how this page's own arithmetic pruning compares to the other nine entries' structural rejection rules.