The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S {\displaystyle S} of integers and a target-sum T {\displaystyle T} , and the question is to decide whether any subset of the integers sum to precisely T {\displaystyle T} . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example:
The variant in which all inputs are positive. The variant in which inputs may be positive or negative, and T = 0 {\displaystyle T=0} . For example, given the set { − 7 , − 3 , − 2 , 9000 , 5 , 8 } {\displaystyle \{-7,-3,-2,9000,5,8\}} , the answer is yes because the subset { − 3 , − 2 , 5 } {\displaystyle \{-3,-2,5\}} sums to zero. The variant in which all inputs are positive, and the target sum is exactly half the sum of all inputs, i.e., T = 1 2 ( a 1 + ⋯ + a n ) {\displaystyle T={\frac {1}{2}}(a_{1}+\dots +a_{n})} . This special case of SSP is known as the partition problem. SSP can also be regarded as an optimization problem: find a subset whose sum is at most T, and subject to that, as close as possible to T. It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice. SSP is a special case of the knapsack problem and of the multiple subset sum problem.
Computational hardness The time complexity of SSP depends on two parameters:
n - the number of input integers. If n is a small fixed number, then an exhaustive search for the solution is practical. L - the precision of the problem, stated as the number of binary place values that it takes to state the problem. If L is a small fixed number, then there are dynamic programming algorithms that can solve it exactly. As both n and L grow large, SSP is NP-hard. The complexity of the best known algorithms is exponential in the smaller of the two parameters n and L. The problem is NP-hard even when all input integers are positive (and the target-sum T is a part of the input). This can be proved by a direct reduction from 3SAT. It can also be proved by reduction from 3-dimensional matching (3DM):
We are given an instance of 3DM, where the vertex sets are W, X, Y. Each set has n vertices. There are m edges, where each edge contains exactly one vertex from each of W, X, Y. Denote L := ceiling(log2(m+1)), so that L is larger than the number of bits required to represent the number of edges. We construct an instance of SSP with m positive integers. The integers are described by their binary representation. Each input integer can be represented by 3nL bits, divided into 3n zones of L bits. Each zone corresponds to a vertex. For each edge (w,x,y) in the 3DM instance, there is an integer in the SSP instance, in which exactly three bits are "1": the least-significant bits in the zones of the vertices w, x, and y. For example, if n=10 and L=3, and W=(0,...,9), X=(10,...,19), Y=(20,...,29), then the edge (0, 10, 20) is represented by the number (20+230+260). The target sum T in the SSP instance is set to an integer with "1" in the least-significant bit of every zone, that is, (20+21+...+23n-1). If the 3DM instance has a perfect matching, then summing the corresponding integers in the SSP instance yields exactly T. Conversely, if the SSP instance has a subset with sum exactly T, then, since the zones are sufficiently large so that there are no "carries" from one zone to the next, the sum must correspond to a perfect matching in the 3DM instance. The following variants are also known to be NP-hard:
The input integers can be both positive and negative, and the target-sum T = 0. This can be proved by reduction from the variant with positive integers. Denote that variant by SubsetSumPositive and the current variant by SubsetSumZero. Given an instance (S, T) of SubsetSumPositive, construct an instance of SubsetSumZero by adding a single element with value −T. Given a solution to the SubsetSumPositive instance, adding the −T yields a solution to the SubsetSumZero instance. Conversely, given a solution to the SubsetSumZero instance, it must contain the −T (since all integers in S are positive), so to get a sum of zero, it must also contain a subset of S with a sum of +T, which is a solution of the SubsetSumPositive instance. The input integers are positive, and T = sum(S)/2. This can also be proved by reduction from the general variant; see partition problem. The analogous counting problem #SSP, which asks to enumerate the number of subsets summing to the target, is #P-complete.
Exponential time algorithms There are several ways to solve SSP in time exponential in n.
Inclusion–exclusion The most naïve algorithm would be to cycle through all subsets of n numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O ( 2 n ⋅ n ) {\displaystyle O(2^{n}\cdot n)} , since there are 2 n {\displaystyle 2^{n}} subsets and, to check each subset, we need to sum at most n elements. The algorithm can be implemented by depth-first search of a binary tree: each level in the tree corresponds to an input number; the left branch corresponds to excluding the number from the set, and the right branch corresponds to including the number (hence the name Inclusion-Exclusion). The memory required is O ( n ) {\displaystyle O(n)} . The run-time can be improved by several heuristics:
… excerpt ends here. Continue reading the full article.
