Subset sums

Computer Science Level 4

In the following sequence of 30 integers, determine how many subsets (including the empty one) have a sum between -700 and 700 inclusive.


The answer is 521259556.

View wiki
Thaddeus Abiy by Thaddeus Abiy , 25, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Piotr Idzik
Apr 22, 2020

My approach using dynamic programming. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
def fun(in_data, min_val, max_val):
    """
    returns the number of ways of summing up, the numbers in in_data in such a way
    that the result is [min_val, max_val]
    """
    res_data = dict()
    def inner(ind_val, sum_val):
        """
        returns the number of ways of summing up the numbers in_data[ind_val], ... in_data[-1]
        in such a way, that the result is equal to sum_val
        """
        nonlocal res_data
        if (ind_val, sum_val) in res_data:
            res = res_data[(ind_val, sum_val)]
        else:
            if ind_val >= len(in_data):
                if sum_val == 0:
                    res = 1
                else:
                    res = 0
            else:
                res = inner(ind_val+1, sum_val-in_data[ind_val]) + inner(ind_val+1, sum_val)
            res_data[(ind_val, sum_val)] = res
        return res
    res_val = 0
    for _ in range(min_val, max_val+1):
        res_val += inner(0, _)
    return res_val

DATA = [-317, 75, -249, -261, -322, 474,
        370, -5, 96, -650, -213, -149,
        -180, -274, 442, 648, 64, -450,
        284, -658, 67, 398, 19, -515,
        -14, 330, -552, 693, -120, 347]
MIN_VAL = -700
MAX_VAL = 700
RES = fun(DATA, MIN_VAL, MAX_VAL)
print(RES)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
James Moors
Jul 31, 2015

Not the most efficient python code I've ever written, but it does the job. 

from itertools import combinations as comb, chain
nums = [-317, 75, -249, -261, -322, 474, 370, -5, 96, -650, -213, -149, -180, -274, 442, 648, 64, -450, 284, -658, 67, 398, 19, -515, -14, 330, -552, 693, -120, 347]

total = 0

#Use chain to obtain the powerset of nums
subnums = chain.from_iterable(comb(nums,n) for n in range(31))

#Run through them all. Check if valid
for i in subnums:
    if sum(i) > -701 and sum(i) < 701: total +=1
print total
0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...