The largest set with values from 0 to 1000 which has no two subsets with equal sum has 9 elements, e.g.:
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512}
If you add a tenth element, then it will be equal to the sum of a subset of the nine previous values.
If you find two subsets with equal sum after you have excluded more than 9 elements, then two equal sums from the excluded elements can be added to form greater equal sums; this means that you should never exclude more than 9 elements.
The sum of the excluded elements in in the range 0 to 1000. Building a sieve to check which values in this range can be formed with the elements in the set will take at most 50 × 1000 steps. (We can store the minimum number of values that add up to each sum instead of a boolean, and use that to include only sums which can be made with 9 or fewer elements.)
If we then look at the sums of excluded numbers from small to large, that means looking at the sums of included numbers from large to small. For each sum of excluded values, we check which (up to 9) elements can form this sum (obviously not a trivial step, but we know the number of elements is between the minimum value as stored in the sieve, and 9), and this gives us the set of excluded and therefor also the set of included numbers. Then we use a similar sieve technique to check whether the included numbers can form the half sum; this will be in the range 1 to 500 and take at most 50 × 500 steps.
In all this, there is of course the odd/even-ness to take into account: if the total sum is odd, a subset with an odd sum has to be excluded; if the total sum is even, only subsets with an even sum have to be excluded.
I haven't really figured out how to generate worst-case input for this, so it's hard to judge the worst-case complexity; but I think the average case should be feasible.
Here are some of the parts in action. First, the sieve to find the sums of the sets of up to 9 values which can be excluded (and have the right odd/even-ness) tested with 20 values with a sum of 999:
function excludedSums(values) {
var sieve = [0];
for (var i in values) {
var temp = [];
for (var j in sieve) {
if (sieve[j] == 9) continue;
var val = values[i] + Number(j);
if (!sieve[val] || sieve[j] + 1 < sieve[val]) {
temp[val] = sieve[j] + 1;
}
}
for (var j in temp) {
sieve[j] = temp[j];
}
}
var odd = values.reduce(function(ac, el) {return ac + el}, 0) % 2;
for (var i in sieve) {
if (Number(i) % 2 != odd) delete sieve[i];
}
return sieve;
}
var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSums(set);
for (var i in result) document.write(i + ", ");
Next, the sets of up to 9 values with a certain sum. In the example above, we see that e.g. one or more sets with the sum 99 can be excluded; let's find out what these sets are:
function excludedSets(values, target) {
var sieve = [[[]]];
for (var i in values) {
var temp = [];
for (var j in sieve) {
var val = values[i] + Number(j);
if (val > target) continue;
for (var k in sieve[j]) {
if (sieve[j][k].length < 9) {
if (!temp[val]) temp[val] = [];
temp[val].push(sieve[j][k].concat([values[i]]));
}
}
}
for (var j in temp) {
if (!sieve[j]) sieve[j] = [];
for (var k in temp[j]) {
sieve[j].push(temp[j][k].slice());
}
}
}
return sieve[target];
}
var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSets(set, 99);
for (var i in result) document.write(result[i] + "<br>");
(You'll see a few duplicates in the output, because e.g. the value 49 appears three times in the set.)
Now let's test whether the set without excluded values can be split in two. We see that the sum 99 can be formed e.g. by values 87 and 12, so we exclude these from the set, and get a set of 18 values with the sum 900. Now we check whether the half sum 450 can be formed by adding values from the set:
function sumPossible(values, target) {
var sieve = [true];
for (var i in values) {
var temp = [];
for (var j in sieve) {
var val = values[i] + Number(j);
if (val < target) temp[val] = true;
else if (val == target) return true;
}
for (var j in temp) sieve[j] = temp[j];
}
return false;
}
var set = [40,7,112,15,96,25,49,49,31,39,8,79,40,73,49,63,55,70];
document.write(sumPossible(set, 450));
So 450 is one of the possible half-sums for this set. Obviously it's not the largest one, because we randomly picked the sum 99 to exclude as an example, instead of iterating over all sums from small to large; in fact the first option, excluding value 7, would have led to the maximum half-sum 496.
It should be noted that the larger the set, the more likely it is that the set can be split in half (if it has an even sum, or with the smallest odd value removed if it has an odd sum). A test with millions of sets of random values with an even sum up to 1000 revealed not a single set that couldn't be split in half, for any set size above 28. (It is of course possible to craft such a set, e.g. 49 ones and a single 51.)
