Hoempa wrote:You may consider the use of a list in your program. The idea is that you construct the set by using the needed sum of every subset, instead of puzzling arround. This way, it would be more of searching for the solution, rather than calculating the options. I'm not sure about the efficiency. Perhaps, you could construct all possibilities to expres the sum of a subset as a sum. e.g. 106=80+26=80+20+6... until you have terms that can be an element of your set.
The restriction on the possible values of the elements seem useful, by looking at the last digit of the sums.
The complexity is something like where you have $n_1$ 1s, 2s, ..., 80s. (I have divided by 250 here.)
This is, technically, polynomial rather than exponential, and the constants aren't too bad. In the worst case with n elements it takes time (n/16+1)^16 which is certainly doable. You could improve on that by taking some small elements and building all possible values from them, storing this in an array, then looping over all the possibilities for the others and checking if the total you get is within one of those amounts of the total. This, if I'm not mistaken, could improve complexity to though (1) the constant gets worse; time probably doesn't improve much until n > 10 or n > 15; and (2) this can take a decent bit of memory if n is large.