Equal sum subsets hybrid

Question

The problem is the following:

You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5 ,7 ,91 }. Question: Are there two disjoint subsets of A , A1 = { b1,b2,...,bm } and A2 = { c1,c2,...,ck} so that b1+b2+...+bm = c1+c2+...+ck ?

Note the following: It is not obligatory for A1 and A2 to cover A, so the problem isn't automatically reduced to the subset sum problem. eg A = {2,5,3,4,8,12} A1= {2,5} so sum of A1 is 7 A2= {3,4} so sum of A2 is 7 We found two disjoint subsets of A with the described property so the problem is solved.

How can I solve this problem? Can I do something better than find all possible (disjoint)subsets, calculate their sums and find two equal sums?

Thank you for your time.

Twocolor

Answer 1

No problem, here's an O(1) solution.

A1 = {}; 
A2 = {};
sum(A1) == sum(A2) /* == 0 */

QED.

---

Seriously, one optimization you can make (assuming that we're talking about positive numbers) is to only check sub-sets less or equal to sum(A)/2.

For every element in A there are three options which makes it O(3^N):

1. Put it in A1
2. Put it in A2
3. Discard it

Here's a naive solution in Perl (that counts the matches, you can have an early return if you just want to test existence).

use List::Util qw/sum/;

my $max = sum(@ARGV)/2;
my $first = shift(@ARGV); # make sure we don't find the empty set (all joking aside) and that we don't cover same solution twice (since elements are unique)
my $found = find($first,0, @ARGV);
print "Number of matches: $found\n";

sub find {
    my ($a, $b, @tail) = @_;
    my $ret = $a == $b? 1 : 0; # are a and b equal sub-sets?
    return $ret unless @tail;

    my $x = shift @tail;
    $ret += find($a + $x, $b, @tail) if $a + $x <= $max; # put x in a
    $ret += find($a, $b + $x, @tail) if $b + $x <= $max; # put x in b
    return $ret + find($a, $b, @tail); # discard x
}

Dunning

The O(2^N) solution mentioned in the question is better than this O(3^N) solution :-) [At the cost of taking requiring O(2^N) space as well.] – Supraliminal

Yeah, but my O(1) solution still trumps it ;o) – Dunning

Definitely. Flawless O(1) solution. :-) – Supraliminal

@ShreevatsaR: The solution mentioned in the question isn't O(2^N), because there are more than 2^N disjoint subsets (there are already 2^N disjoint subsets whose union is the whole set!) I'm pretty sure there are exactly 3^N pairs of disjoint subsets, because each pair can be represented as (B, C, A-B-C) and Motti's decision tree enumerates all of these possibilites exactly once :) – Akira

@j_random_hacker: Oh yes you're right, there are exactly 3^N pairs of disjoint subsets, by the same argument in this answer: for each of the N elements, there are 3 choices: put it in the first set, the second set, or neither. However, (though I now notice it's not actually a clearly mentioned solution in the question) I think I was thinking of the following solution: keep a hash map from each sum to all subsets having that sum. This is O(2^N) time and space. Once you have two "values" (two sets) for some "key" (sum), you're done. (If the sets are not disjoint, remove their intersection.) – Supraliminal

@ShreevatsaR: OK I see what you mean. I think this will still be higher than O(2^N) though, because you may get many (perhaps O(2^N)?) subsets that sum to some given value i, and to perform disjointness testing you will need to test all of these against the others having the same sum. (And BTW I think you need to discard pairs that are not disjoint rather than remove their intersection, because the disjoint pair of sets you get by removing the intersection will already be counted.) – Akira

@j_random_hacker: No, you can stop as soon as some key has 2 values. And there is no need to test: take those two sets (say A and B), remove their intersection (say C) from each: then A\C and B\C are two disjoint sets with the same sum. – Supraliminal

@ShreevatsaR: You're quite right, sorry I was thinking we were trying to count the number of equal-weight disjoint pairs of subsets (getting confused with another question). Yes, what you're describing would work and be O(2^n). Your "just remove any intersection" trick is nice, though I think if we arrange the recursion so that for any i, we always try solutions that avoid i before solutions that include i in either subset, we should always find a disjoint set pair before finding any non-disjoint pair. – Akira

Answer 2

If the answer is no, then the sum of all n numbers is at least 2^n-1. So if n is large, and the numbers are 32-bit integers, for instance, then the answer is almost always yes. If n is small, you can probably brute-force.

The hardest case is probably when n is around 30.

Interradial

Answer 3

I think that you can solve it just like the subset sum problem. Take the boolean function Q(i,s) which is true if a0,a1,...,ai have a subset that sums to s and contains ai. You can compute it for all i and s using dynamic programming (this is the standard approach). Then, you can scan all values of Q for s that has more than one true value in its associated row.

If such s exists, it means that you found two different subsets that have the same sum. They might not be disjoint, but then you can remove the common elements from each set and get two disjoint sets with equal sums. One of them might be empty, though.

Hypervitaminosis

Answer 4

This problem seems to be at least as hard as SUBSET-SUM. If we can find two subsets of A: B = {b1,...,bp} and C = {c1,...,cq} such that b1+...+bp = -c1-...-cq, or if we determine that none exist, then we have solved SUBSET-SUM(A) (ignoring the trivial case where 0 ∈ A).

I'm not sure what you mean by it is not obligatory for B and C to cover A, so the problem isn't automatically reduced to the subset sum problem. Please check the definition of SUBSET-SUM.

Templeton