Is there a known, fast algorithm for counting all subsets that sum to below a certain number?
Subset below-sum appears to be NP-Hard. This is informal, but consider, if you can solve subset below-sum in polynomial time, you can solve subset sum in polynomial time.


Given: does any subset of $S$ sum to exactly $n$?
Let $A$ be $subset\_below\_sum(n)$ and $B$ be $subset\_below\_sum(n + 1)$. If $B - A \gt 0$, the answer is yes, otherwise, the answer is no.