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.