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 \( \lfloor \log_2 k \rfloor \) for any \( W \)-bit value \( k \), and that all the members of \( S \) are \( W \)-bit numbers and that \( W\ge\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.

Comments: