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(log

_{2}(k)) for any W-bit value k, and that all the members of S are W-bit numbers and that W ≥ log

_{2}|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.

## Error

Your reply will be screened

Your IP address will be recorded