0xDE (11011110) wrote,

The missing subset sum

Here's a cute algorithmic puzzler that occurred to me yesterday, though perhaps it was long-known to others.

Let S be a set (or multiset) of positive integers. Describe an efficient algorithm for finding the smallest positive integer x such that x is not the sum of some subset of S.

Using dynamic programming to test each possible subset sum isn't good enough; I want something strongly polynomial. Or, to be really concrete about it, let's suppose that you have a computer in which W-bit integers can be added, subtracted, and compared in constant time, that additionally you have a constant time operation to compute floor(log2(k)) for any W-bit value k, and that all the members of S are W-bit numbers and that W ≥ log2|S|; I want an algorithm that runs in time O(|S|+W) in this model.

If you get stuck, the characterization of practical numbers might give you a hint.
Tags: algorithms
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded