algorithm - 划分整数集

Question

我对算法问题的解决方案有疑问，如下所述。

我们有一组整数（例如数组）。我们的任务是将它们分成总和彼此相等的组（它们不必具有相同数量的元素）。我认为原始集合不能被划分，我们必须给出“不可能划分”的答案。

例如： Set Ais given [-7 3 3 1 2 5 14]。答案是[-7 14], [3 3 1], [2 5]。

似乎很容易说什么时候肯定是不可能的。当原始集的总和不能被 3 整除时：sum(A) % 3 != 0。

你知道如何解决这个问题吗？

Answer 1

这是分区问题的3 分区问题变体，区别在于经典分区问题将集合分成两个集合（不是三个），它们的总和彼此相等。这个问题是 NP 完全的，所以你几乎肯定不会找到它的多项式时间解；2 分区问题具有伪多项式时间解，但 3 分区问题没有。

有关如何将 2 分区算法调整为 3 分区算法的概要，请参阅此答案。另请参阅本文以获取并行解决方案。