# 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?

• There is no fast algorithm, unless P=NP. Jan 30 '16 at 0:36
• A counting problem can never be in NP, by definition.
– Raphael
Jan 30 '16 at 13:10

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.
• This doesn't show that the problem is NP-hard. It only shows that it's not in P unless P=NP. It could be #P-hard, though. Jan 30 '16 at 0:35
• @YuvalFilmus : ​ ​ ​ It also shows that it's NP-hard under non-adaptive 2-query reductions. ​ (Although your other sentences are correct.) ​ ​ ​ ​ ​ ​ ​ ​
– user12859
Jan 30 '16 at 1:29

The similar problem #Subset-Sum, in which we want to count the number of subsets summing to some target, is #P-complete (this is implied by this paper). This hints that your problem, which is clearly in #P, might also be #P-complete.

• Can you explain the correspondence? For instance, suppose $n=18$, so your plan is to add 16 to the set. Why does a subset summing to $17$ in the new set correspond to a subset summing to at most $17$ in the original set? For instance, consider a subset summing to 15 in the original set; what does it correspond to in the new set? I'm not seeing it at the moment...
– D.W.
Jan 30 '16 at 8:43
• Right, this only works when $n-2$ is of the form $2^m-1$. But this doesn't sound like an insurmountable hurdle. Jan 30 '16 at 8:44
• You have what we're interested in backwards. ​ ​
– user12859
Jan 30 '16 at 9:25
• @RickyDemer I don't think so. Jan 30 '16 at 9:29
• To be a parsimonious reduction from #-Subset-Sum to the OP's problem, we would need solutions in the new set to correspond to solutions in the old set. ​ Solutions in the new set are those summing to less than n-1, and solutions in the original set are those summing to exactly n-1. ​ You have things the other way around. ​ ​ ​ ​
– user12859
Jan 30 '16 at 9:40