# Counting the number of subsets with positive sum

I have some constant vector $$\mathbf{s}$$ on $$n$$ dimensions, where every element of $$\mathbf{s}$$ is a real number, and I would like to multiply it by every possible $$n$$-dimensional binary vector $$\mathbf{v}_j\ (0\leq j < 2^n)$$.

I only care about whether $$\mathbf{s}\cdot \mathbf{v}_j > 0$$. I would like to count all of the times this condition holds.

Question: As the naive algorithm has complexity $$O(2^n)$$, it blows up fast. What are my options for optimizing this for large $$n$$?

• So, you basically want to know how many subsets of $\mathbf{s}$ sum to a positive value? – ryan Apr 1 at 22:53
• You want to determine the expected value of a linear threshold function (LTF). There is some literature on that. – Yuval Filmus Apr 2 at 4:20
• You can use a meet-in-the-middle approach to get an $O(2^{n/2})$ algorithm: calculate all sums of each half of the vector, then run a two pointer algorithm. – Yuval Filmus Apr 2 at 4:22
• Additionally, if the real numbers can be expressed as rationals with some small common denominator, expressing it as a knapsack problem will help. If it is acceptable to round to such numbers (e.g., to three digits after the decimal point), the same applies. – Gassa Apr 2 at 11:03
• @ryan Thanks for reformulating -- that is correct. – Jake Brukhman Apr 2 at 14:53

Suppose that you could solve this in $$T(n)$$. Given a list of positive integers $$a_1,\ldots,a_n$$ and a target $$T$$, consider the two instances $$a_1,\ldots,a_n,-T$$ and $$a_1,\ldots,a_n,-T+1$$. Denoting by $$N(\cdots)$$ the number of positive sums, we get:
• $$N(a_1,\ldots,a_n,-T)$$ is the number of subsets of $$\{a_1,\ldots,a_n\}$$ whose sum is larger than $$T$$.
• $$N(a_1,\ldots,a_n,-T+1)$$ is the number of subsets of $$\{a_1,\ldots,a_n\}$$ whose sum is at least $$T$$.
By comparing these two numbers, you can solve SUBSET-SUM in time $$T(n+1)$$.
There is a simple $$O(2^{n/2})$$ algorithm, which proceeds as follows. We break the array $$s_1,\ldots,s_n$$ into two equal halves. We compute an ordered list $$A_1,\ldots,A_{2^{n/2}}$$ of all sums of the first half, and an ordered list $$B_1,\ldots,B_{2^{n/2}}$$ of all sums of the second half. This takes time $$O(2^{n/2})$$ if done carefully (by iterative merging). We put a pointer $$j$$ at $$B_{2^{n/2}}$$, and decrease it until $$A_1 + B_j \le 0$$. The value of $$j$$ tells us the number of pairs $$(1,j')$$ satisfying $$A_1 + B_j > 0$$. Then we do the same for $$A_2$$ — note that we can start the scan at the current value of $$j$$; and so on. This phase also takes $$O(2^{n/2})$$.