algorithm - 等和子集混合

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 的和是 7A2= {3,4} 所以 A2 的总和是 7我们发现 A 的两个不相交的子集具有所描述的属性，因此问题得到解决。

我该如何解决这个问题？除了找到所有可能的(不相交的)子集、计算它们的总和并找到两个相等的总和之外，我还能做些什么吗？

感谢您的宝贵时间。

Answer 1

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

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

QED。

---

说真的，您可以进行的一项优化(假设我们讨论的是正数)是仅检查小于或等于 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
}