subset-sum

You are given a pile of numbered coins and a target amount, and you must answer: can I pick SOME of these coins (any subset) that add up exactly to the target? That is subset-sum. It is the purest of the number-packing problems, and it is the gateway to PARTITION (split the numbers into two equal-sum halves) and to KNAPSACK (pack the most value under a weight limit).

Formally, subset-sum takes a set of positive integers S and a target t, and asks whether some subset of S sums exactly to t. It is in NP: the subset itself is the certificate, and a verifier just adds up its elements and compares to t, in polynomial time. PARTITION is the special case asking whether S can be split into two parts of equal sum, which is subset-sum with target equal to half the total. Both are NP-complete, reachable by reductions from 3-SAT in which carefully chosen large numbers encode logical choices so that a target is hit exactly when a clause-satisfying assignment exists.

Subset-sum carries a famous and instructive subtlety about what 'polynomial' means. There is a dynamic-programming algorithm running in time proportional to n times t (number of items times target). That looks polynomial, but it is not polynomial in the INPUT SIZE, because t is written in binary using only about log t bits, so n times t is exponential in the number of bits. Such an algorithm is called pseudo-polynomial: fast when the numbers are small, exponential when they are large. Subset-sum is therefore NP-complete in the strong sense relevant to large numbers, a textbook lesson that 'size of input' means number of bits, not numeric magnitude.