Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - Equal sum subsets hybrid

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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
";

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
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...