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?