Is there a known, fast algorithm for counting all subsets that sum to below a certain number? I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum:


Given a set of integers, $S$, and a target number, $n$, what is the number of subsets of $S$ that sum to less than $n$?


For example, if $S$ is $\{1, 2, 3, 7, 7, 15\}$, and $n$ is $20$, the answer is $38$.

Is this an NP-Complete problem? If not, what is a fast algorithm to compute the answer?
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.