count all subsets of integers (including negative) that sum to x

Question

I am given an array of max length 40 containing integers in [-10^9;10^9]. I am also given the expected sum X which lies in [0;10^9]. Now I am supposed to give the total amount of subsets that sum to X. I can't figure out a way to deal with the negative numbers. I first tried the brute-force approach which works fine for small input arrays but is unusable for large ones:

auto r = 0ULL;
for(auto i = 0ULL; i < (1ULL << n) - 1ULL; ++i) {
    auto x = 0ULL;
    for(auto j = 0ULL; j < n; ++j) {
        if(i & (1ULL << j)) {
            x += values[j];
        }
    }
    r += x == sum;
}
cout << r << '\n';

Then I tried memorizing the intermediate results of the additions so I don't have to calculate them more then once for the same elements. But that consumes ALOT of space ( should be around 9 TB for inputs of length 40 x) ). Can someone give me a hint on a better approach?

This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, May 25 '20 at 23:00
What techniques were taught in class before this homework assignment was given? Recursion? Loops? Linked lists? Arrays? Something else? If this is a homework assignment it means that you are obviously expected to use a specific technique for solving it. So, can you explain what techniques were presented in class, that this homework assignment is expected to demonstrate? — Sam Varshavchik, May 25 '20 at 23:02
http://panzi.github.io/numbers-js/ Someone has done this for +-*/ so just cut down their solution. — QuentinUK, May 25 '20 at 23:10
this is an advanced lecture that's supposed to give you an introduction to coding competitions, knowing basic programming concepts like you mentioned is expected. — Yamahari, May 25 '20 at 23:11

MBo · Accepted Answer · 2020-05-26T04:24:03.767

Sum range and item count looks too large for dynamic programming due to memory reason.

But limit of 40 items allows to apply something like "meet-in-the-middle" principle.

Separate the first 20 items and count sums for all possible subsets - just walk through 2^20 subsets (including empty one!) (using recursion or binary representation of subset number or some other way) and write sums in the map containing pairs (sum, count).

Do the same for the second half. Note that size of maps is quite reliable.

Walk though the first map keys and look for corresponding keys from the second map. Pseudocode:

for sum in map1:
    if map2.contains(X - sum):
        result += map1[sum] * map2[X - sum]

score 1 · Answer 2 · answered May 25 '20 at 23:05

1

Hint: there is a recurrence you can use. Let num_subsets[i][k] be the number of subsets of values[0], values[1], ..., values[i] that can sum to k. Then

num_subsets[i][k] = num_subsets[i - 1][k – values[i]] + num_subsets[i - 1][k]

Then num_subsets[n-1][x] is your answer.

answered May 25 '20 at 23:05

orlp

112,504
36
218
315

Hm, doesnt this assume strictly positive inputs? If values[i] is negative the sum increases – Yamahari May 25 '20 at 23:24
@Yamahari No that's perfectly fine. – orlp May 25 '20 at 23:25
@orlp the data range is big, the 2d array can lead to huge space cost. – Kun Hu May 25 '20 at 23:51
@KunHu I never mentioned a 2D array? You can implement `num_subsets[i][k]` in many ways, a recursive function, hash maps, etc. – orlp May 25 '20 at 23:58
@orlp the number of different subset sums is still huge. For example, when i is 30, and subset size is 15, there can be 155,117,520 different subsets (sums), don't we need to store all these results? – Kun Hu May 26 '20 at 00:17
@KunHu If `k` is greater than all of them, potentially, yes. That's why this dynamic programming solution is pseudo-polynomial time. If `k` grows too large to store this problem is NP-hard. But 10^9 isn't at that point yet, that's around 8 gigabytes. – orlp May 26 '20 at 00:19

count all subsets of integers (including negative) that sum to x

2 Answers2