algorithm - 二进制数的子集和

Question

我有 X 个长度为 Y 的二进制数，想看看它们加起来是否等于特定的总和 K。

我对子集和问题的动态解决方案做了一些研究；但是，我认为这个具体问题出现了转折。

将两个长度为 Y 的二进制数相加并将和的长度限制为 Y 有时会从和中减去 2^(Y)(如果存在溢出)。由于两个二进制数相加有时会导致溢出，比如相加:

10000000000000000000000000000000000000010
10000000000000000000000000000000000000010

将产生总和

00000000000000000000000000000000000000100

因此，在某些情况下，增加数字实际上会降低当前总和。

此刻，我正在用头撞墙。任何提示或指示如何解决这个特定版本的子集和问题？

更新:

我可以使用的东西没有真正的限制。我唯一的目标是用大约 50 个长度为 ~40 的二进制数产生最快的运行时间

Answer 1

您可以使用中间相遇技术。

1. 将您的初始数组分成两半(如果总共有 50 个数字，则分成 25 个数字)。

2. 对于每一半，生成所有可能的子集总和(它需要类似O(2^n) 或O(2^n * n) 的时间). n = 25应该可行(n是二分之一的大小)。

3. 对于前半部分的每个可能的总和，使用哈希表检查后半部分是否有合适的总和(使用 A + B = target (mod M)表示 B = target - A (mod M))。