Subset Sum

The subset sum problem (SSP) is a classic problem in theoretical computer science and combinatorial optimization.

It consists of determining whether there exists a subset of a given set of integers whose sum equals a given target value.

Formally, given a set $ A = \{n_1, n_2, \ldots, n_n\} $ and a target $ N $, the goal is to find a subset $ B \subseteq A $ such that the sum of the elements of $ B $ equals $ N $, i.e., $ \sum n_{i \subseteq B} = N $

— Naive approach (brute force): Test all possible combinations of subsets. This method has an exponential complexity of $ O(2^n) $, making it inefficient for large sets.

— Dynamic programming: Use a table to store the sums feasible with the subsets. The complexity is $ O(n \times N) $, where $ n $ is the size of the set and $ N $ is the target value.

— Approximation algorithms: For large instances, algorithms like Meet-in-the-Middle reduce the complexity to $ O(2^{n/2}) $

The knapsack problem generalizes the sum of subsets by assigning a weight and a value to each element.

In the knapsack problem, the goal is to maximize the total value without exceeding a given capacity, whereas the sum of subsets focuses solely on the sum of the elements.

By allowing repetition of elements in the sum of subsets, then the subset problem is a variant of integer partitions restricted to a given set.