Subset sum problem

Variants and related problems

The subset sum family includes several closely related formulations:

• Decision version: does a subset exist with sum exactly x?
• Optimization version: find a subset whose sum is as close as possible to x without exceeding it.
• Counting version: how many distinct subsets sum to x? (a #P-type problem).
• Bounded and unbounded variants: items may have multiplicities or be reusable.
• Special cases: Partition (target = total/2), knapsack (weights with values), and the change-making problem.

These relationships make subset sum a key subproblem in combinatorial optimization and number-theoretic decision problems; see further reading in general references and example datasets at collections.

Complexity and algorithms

The decision problem is NP-complete in general, meaning no polynomial-time algorithm is known that solves every instance. However, it is "weakly" NP-complete: dynamic programming yields a pseudo-polynomial-time algorithm whose running time depends on the numeric value of the inputs (typically O(n·W) where W is the target or sum magnitude) rather than just the number of items. This distinction matters: when numbers are small or encoded in unary the dynamic program becomes practical.

Common algorithmic approaches include:

• Dynamic programming (table or bitset) for pseudo-polynomial performance.
• Meet-in-the-middle methods that split the set and combine partial sums in about O(2^{n/2}) time, effective for moderate n.
• Branch-and-bound and pruning heuristics used in exact solvers for many real instances.
• Approximation and heuristic methods or reductions to SAT/ILP for large practical instances. See algorithmic surveys at algorithm resources.

History and applications

Subset sum has been studied since the early development of computational complexity theory and is one of the canonical NP-complete problems. It has practical uses in resource allocation, scheduling, cryptography and combinatorial design. Historically, certain knapsack-style cryptosystems (e.g., the Merkle–Hellman knapsack) were based on subset-sum-like constructions; some of those cryptosystems were later broken, which illustrates both the practical interest and the subtleties involved in using combinatorial problems for security. For historical and survey material see further reading.

Examples, distinctions and notable facts

An important special case is the partition problem: deciding whether a multiset can be split into two parts with equal sum is the same as asking whether some subset sums to half the total. Counting the number of solutions is generally harder (#P-complete), and the existence of a pseudo-polynomial algorithm makes subset sum a useful example when explaining the difference between weak and strong NP-completeness. Practical solvers combine dynamic programming with clever data structures (bitsets, sorted lists of achievable sums) and meet-in-the-middle tradeoffs to handle many realistic instances efficiently.

Because of its simplicity and connections to other combinatorial questions, subset sum remains a central problem both as a theoretical benchmark and as a building block in applied algorithms.