我想出了一个新的算法来解决子集和问题，我认为它是在多项式时间内。告诉我我要么错了要么完全是个天才。
快速入门事实：
子集和问题是一个 NP 完全问题。在多项式时间内求解它意味着 P = NP。
一组长度为 N 的子集的数量为 2^N。
另一方面，长度为 N 的唯一子集的数量最大为整个集合的总和减去最小元素，或者，任何子集可能产生的和的范围在所有负元素的总和之间和所有正元素的总和，因为没有总和可能大于或小于所有正或负总和，当我们添加额外元素时，它们以线性速率增长。
这意味着随着 N 的增加，重复子集的数量呈指数增长，而唯一有用的子集的数量仅线性增加。如果可以设计一种算法来尽早删除重复的子集，我们将在多项式时间内运行。一个简单的例子很容易取自二进制文件。仅从作为 2 的幂的数字，我们可以为任何整数值创建唯一的子集。因此，任何涉及任何其他数字的子集（如果我们有 2 的所有幂）都是重复的和浪费的。通过不计算它们及其导数，我们几乎可以节省算法的所有运行时间，因为与任何整数相比，作为 2 的幂的数字都是对数出现的。
因此，我提出了一个简单的算法，该算法将删除这些重复项并省去计算它们及其所有导数的麻烦。
首先，我们将对只有 O(N log N) 的集合进行排序，并将其分成两半，正数和负数。负数的过程是相同的，所以我将只概述正数（集合现在仅表示正数，只是为了澄清）。
想象一个由 sum 索引的数组，其中包含所有可能的正边结果总和的条目（记住，这只是线性的）。当我们添加一个条目时，值是子集中的条目。就像，数组 [3] = { 1, 2 }。
一般来说，我们现在开始枚举集合中的所有子集。我们通过从一个长度的子集开始，然后添加到它们来做到这一点。当我们拥有所有独特的子集时，它们形成一个数组，我们只需按照 Horowitz/Sahni 中使用的方式迭代它们。
现在我们从“第一代”价值观开始。也就是说，如果原始数据集中没有重复的数字，则保证这些值中没有重复。也就是说，所有单值子集，以及集合的所有长度减去一个长度的子集。这些可以通过对集合求和并依次减去每个元素来轻松生成。此外，集合本身是有效的第一代总和和子集，以及子集的每个单独元素。
现在我们做第二代价值观。我们遍历数组中的每个值和每个唯一子集，如果没有，我们添加它并计算新的唯一子集。如果我们有重复，就会发生乐趣。我们将其添加到碰撞列表中。当我们添加新的子集时，我们检查它们是否在冲突列表中。我们以不太理想的（通常更大，但可以是任意的）相等子集为关键。当我们添加到子集时，如果我们会产生碰撞，我们什么也不做。当我们来添加更理想的子集时，它会错过检查并添加，生成公共子集。然后我们只是重复其他几代人。
通过以这种方式删除重复的子集，我们不必继续将重复项与集合的其余部分组合，也不必继续检查它们是否有冲突，也不必对它们求和。最重要的是，通过不创建非唯一的新子集，我们不会从它们生成新子集，我相信这可以将算法从 NP 转变为 P，因为子集的增长不再是指数级的——我们丢弃它们中的绝大多数在它们可以在下一代中“复制”并通过与其他非重复子集组合来创建更多子集之前。
我认为我没有很好地解释这一点。我有照片……它们在我的脑海里。重要的是，通过丢弃重复的子集，您几乎可以消除所有的复杂性。
例如，想象一下（因为我是手工做这个例子）一个简单的数据集，它从 -7 到 7（不是零），我们的目标是零。排序和拆分，所以我们剩下 (1, 2, 3, 4, 5, 6, 7)。总和是 28。但 2^7 是 128。所以 128 个子集适合 1 .. 28 的范围，这意味着我们事先知道 100 个集合是重复的。如果我们有 8 个，那么我们将只有 36 个插槽，但现在有 256 个子集。所以你可以很容易地看到，现在被骗的数量是 220，是以前的两倍多。
在这种情况下，第一代的值为 1, 2, 3, 4, 5, 6, 7, 28, 27, 26, 25, 24, 23, 22, 21，我们将它们映射到它们的组成部分，所以
1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 = { 1, 2, 3, 4, 5, 6 }
现在要生成新的子集，我们依次获取每个子集并将其添加到彼此的子集中，除非它们具有相互子集，例如 28 和 27 具有hueg 相互子集。因此，当我们取 1 并将其添加到 2 时，我们得到 3 = { 1, 2 } 但请等待！它已经在数组中。这意味着我们现在不会将 1 添加到任何已经包含 2 的子集中，反之亦然，因为这是 3 的子集的重复。
现在我们有
1 = { 1 }
2 = { 2 }
// Didn't add 1 to 2 to get 3 because that's a dupe
3 = { 3 } // Add 1 to 3, amagad, get a duplicate. Repeat the process.
4 = { 4 } // And again.
...
8 = { 1, 7 }
21? Already has 1 in.
...
27? We already have 28
现在我们将 2 添加到所有。
1? Existing duplicate
3? Get a new duplicate
...
9 = { 2, 7 }
10 = { 1, 2, 7 }
21? Already has 2 in
...
26? Already have 28
27? Got 2 in already.
3?
1? Existing dupe
2? Existing dupe
4? New duplicate
5? New duplicate
6? New duplicate
7? New duplicate
11 = { 1, 3, 7 }
12 = { 2, 3, 7 }
13 = { 1, 2, 3, 7 }
如您所见，即使我每次都在添加新的子集，但数量只是线性增加。
4？
1? Existing dupe
2? Existing dupe
3? Existing dupe
5? New duplicate
6? New duplicate
7? New duplicate
8? New duplicate
9? New duplicate
14 = {1, 2, 4, 7}
15 = {1, 3, 4, 7}
16 = {2, 3, 4, 7}
17 = {1, 2, 3, 4, 7}
5?
1,2,3,4 existing duplicate
6,7,8,9,10,11,12 new duplicate
18 = {1, 2, 3, 5, 7}
19 = {1, 2, 4, 5, 7}
20 = {1, 3, 4, 5, 7}
21 = new duplicate
现在我们有了范围内的每个值，所以我们停下来，将 1-28 添加到我们的列表中。对负数重复，遍历列表。
编辑：
在任何情况下，这个算法都是完全错误的。具有重复总和的子集不是出于可以从中派生子集的目的的重复，因为它们的到达方式不同——即它们不能被折叠。