algorithm - 给定一个黑盒子找到一个集合的相等划分，如果存在则返回 true

Question

在我准备考试的过程中，我发现了这个我无法解决的问题，也无法在网上找到解决方案。我已经苦苦挣扎了几个小时，试图解决这个问题，但运气不佳。

问题如下:给定一个黑盒子，如果存在集合 S 的 2 个子集 T 和 S/T 且总和相等，则返回 true，如果不存在则返回 false 't，在多项式时间内。

假设给定一个集合 S，上面的黑框找到一个子集 T，其中 T 的总和与 (S/T) 的总和相等。

提前致谢。

Answer 1

对于集合中的每一对数字 A 和 B，您可以进行测试以查看它们是否都在一个有效分区中的同一分区中:从集合中删除 A 和 B 并替换为 C，即A + B 的总和。如果黑盒对新集合返回真，则 A 和 B 必须属于同一分区。如果是，则将 C 保留在集合中。如果不是，请将 A 和 B 放回原位并尝试另一对。

重复直到集合中只剩下 2 个数字，记录您将哪些数字加在一起生成它们。这为您提供了两个分区。