Reduce Subset Sum to Partition

Balance a target subset against its complement without assuming the target is half the total.

Problem

For positive integers $a_1,\ldots,a_m$ and target $T$, reduce SUBSET-SUM to PARTITION. Handle immediately the cases $T>\sum_i a_i$ and define PARTITION as asking whether the multiset can be split into equal-sum parts. Prove correctness and polynomial encoding length.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Let $S=\sum_i a_i$ and add numbers that force a target offset.

Hint 2

The pair $S+T$ and $2S-T$ makes the new total $4S$.

Hint 3

In an equal partition the two added numbers cannot lie on the same side.

Full solution

If $T>S=\sum_i a_i$, output a fixed no-instance such as $\{1,2\}$; positivity makes the source answer no. Otherwise output the multiset

All numbers are positive (if $T=0$, the source is trivially yes and may be mapped separately). Their total is $4S$, so an equal partition gives each side sum $2S$.

If a subset $I$ of the original numbers sums to $T$, place $2S-T$ together with the elements indexed by $I$. Their sum is $2S$. Put all remaining original numbers with $S+T$; their sum is $(S-T)+(S+T)=2S$. Thus a source solution yields a partition.

Conversely, consider an equal partition. The two added numbers cannot be on the same side because their sum is $3S>2S$, the required side total. Hence they are separated. On the side containing $2S-T$, the original numbers on that side must sum exactly $T$. They constitute a subset-sum witness. This proves both implications.

Computing $S$ uses polynomially many binary additions. The new values have magnitude at most $3S$, and $\log S\le \log m+\max_i\log a_i+O(1)$, so each has polynomial encoding length. The mapping itself is polynomial-time. Multiplicity is retained: PARTITION and SUBSET-SUM instances are multisets, so equal values at different positions remain distinct selectable items.

An alternative reduction can add one balancing element involving $|S-2T|$, but it requires a careful case split about which side receives it. The two-marker construction makes the converse transparent. The special cases $T=0$ and $T>S$ should be resolved explicitly rather than allowing a zero or negative “positive integer” in the target instance.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Adding $S-2T$ without handling its sign.
• Failing to prove the marker numbers are separated.
• Measuring output size by numeric magnitude rather than bit length.

Sources and verification

• 2026 transcript 15
• Garey-Johnson, SP12
• Corpus coverage note: No direct merged-summary coverage.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.

Open in the visualization gallery: Subset Sum → Partition