等和子集混合

Question

问题如下:

给你一组正整数{a1,a2,a3,...,an},其中没有相同的数字(a1只存在一次,a2只存在一次,......)例如A = {12,5 ,7,91}.问题:是否有两个不相交的A子集,A1 = {b1,b2,...,bm}和A2 = {c1,c2,...,ck},因此b1 + b2 + ... + bm = c1 + c2 + ... + ck？

请注意以下事项:A1和A2不必覆盖A,因此问题不会自动减少到子集求和问题.例如A = {2,5,3,4,8,12} A1 = {2,5}因此A1的总和是7 A2 = {3,4}所以A2的总和是7我们发现A的两个不相交的子集描述的属性,所以问题解决了.

我怎么解决这个问题？我能做的比找到所有可能的(不相交的)子集更好,计算它们的总和并找到两个相等的总和吗？

感谢您的时间.

Answer 1

没问题，这里有一个O(1)解决方案。

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

量子ED。

说真的，您可以进行的一项优化（假设我们正在讨论正数）是仅检查小于或等于 的子集sum(A)/2。

对于其中的每个元素，A都有三个选项使其成为O(3^N)：

1. 把它放进去A1
2. 把它放进去A2
3. 丢弃它

这是 Perl 中的一个简单的解决方案（对匹配进行计数，如果您只想测试是否存在，可以提前返回）。

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
}