algorithmdynamic-programmingsubset-sum

Getting all distinct subsets from subset sum problem with target T using Dynamic Programming


In the classic subset sum problem, there are a set S and a target t, and the goal is to find a subset of S whose sum is t. This variant has a pseudo-polynomial time solution.

In a variant of the subset sum problem, the goal is to find every subset of S whose sum is t. This variant has no pseudo-polynomial time solution; see answers here: Getting all subsets from subset sum problem on Python using Dynamic Programming. One of the comments explains that in the worst case, when you have N zeroes and the needed sum is also zero, you will need to output all 2^n - 1 subsets - so you can't get better than O(2^n).

What if we do not differentiate between two items of the same value (such that if two sets are composed of some items with the same values, they are considered the same set) --- what is the run-time complexity of outputing all different subsets with sum t?


Solution

  • I believe that the worst case for your revised problem is that the set are all of the integers from -m to m, looking for a sum of 0. This set has no duplicates at all.

    In this case n = 2m+1. Since n and m vary by a constant factor, they are the same as far as big-O is concerned.

    The largest possible sum is m*(m+1)/2 and the smallest is -m*(m+1)/2. That means that the 2^n possible subsets are divided up between O(n^2) possible sums. This creates an immediate lower bound of O(2^n / n^2), which is exponential.

    That lower bound can be improved slightly using the central limit theorem. Consider the case of a random set. It is the sum of n random variables. Each random variable has some mean i and variance (i/2)^2. The sum of the random variables has mean 0, and variance O(n^3). It is therefore approximately a normal distribution with mean 0 and standard deviation that is O(n^(3/2)). Which means that the number of ways to sum to 0 should be O(2^n / n^(3/2)).