给定一个整数数组，创建分区，每个分区中的元素之和为0，并且不形成分区的最大数目

Question

我的规则：

• 允许重复
• 明显允许负数
• 由于我提到了分区，这意味着您不能将数组中的元素放入多个分区中
  • 分区中的元素是子集/不需要是数组的连续块
  • 输入数组中的元素未按排序顺序
  • 输入数组中所有元素的总和将为0（给定条件）

示例：如果A = {-2，-4，-6，+ 6，+ 6}，则B = {{-2，-4,6}，{+ 6，-6}}是最大分区数

仅供参考，我要返回所有分区而不是分区数。

根据我的研究，这似乎是NP难题/完全问题。但是我不确定，如果有人能解释最好的方法（即使很慢），我将不胜感激。一些伪代码也将不胜感激。

谢谢。

Answer 1

我同意问题是NP。用大写的“ ugh”来优化它是很丑的。您可以稍微改善搜索时间，但是我担心它仍然会O（2 ^ N）甚至更糟。

• 将列表分为正数和负数；都排序列表。
• 对于较短列表的每个元素，请在另一个元素中寻找其补语。每个这样的对都是一个分区。这些可以安全地放在解决方案列表中，并从进一步处理中删除。

现在是丑陋的部分。 “相对”蛮力方法是生成每个分区的功率集。总和索引。例如，给定列表2, 3, 4, 7：

 2  [2]
 3  [3]
 4  [4]
 5  [2, 3]
 6  [2, 4]
 7  [7] [3, 4]
 9  [2, 7] [2, 3, 4]
10  [3, 7]
11  [4, 7]
12  [2, 3, 7]
13  [2, 4, 7]
14  [3, 4, 7]
16  [2, 3, 4, 7]

现在查找正列表和负列表之间的所有abs（sum（subset））匹配项。这些构成您解决方案空间的选择。从这一点上，我最好的建议是将set coverage problem应用于此。您必须稍作调整以获取重复的值。

Answer 2

这肯定具有NP硬性的感觉。特别地，是否可以进行2个分区与1个分区的问题是关于除最后一个元素之外的所有元素的适当子集是否累加到最后一个元素的负数的问题，这是子集和问题的变体。因此，即使验证是否无法通过拆分一个分区来进一步改善答案，也可能是NP完整的！

但是，实际上如何解决这个问题？

步骤1产生了一个数据结构，该数据结构表示所有可能的分区，包括总和为0的第一个元素。可以像在标准子集总和算法中一样解决。通过双向链接列表的思想，我们可以从中获取信息。 （双向链表通常与您的数组大小乘以找到的不同总和数成正比，但是解码时，它可能导致指数级的分区。

双向链表可以使您旋转，所以您可能希望按如下方式使用语法糖：

from collections import namedtuple
Node = namedtuple('Node', ['ind', 'prev'])
Paths = namedtuple('Paths', ['node', 'prev'])

ind是数组的索引，node始终是Node，prev始终是Paths或None。

现在Node说“在以下先前的选择中包括此索引和任何有效路径”。 Paths说：“这里有一个节点通向这里，还有其他方法的先前路径。”

通过此操作，我们可以执行以下操作：

# We only want paths that take the 0th index.
ways_to_get_to_n = {elements[0], Paths(Node(0, None), None)}

for i in range(1, len(elements)):
    element = elements[i]
    new_ways_to_get_n = {}
    for value, ways in ways_to_get_n.items():
        new_ways_to_get_n[value] = ways
    for value, ways in ways_to_get_n.items():
        if value + element not in new_ways_to_get_n:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), None)
        else:
            new_ways_to_get_n[value + element] = Paths(Node(i, ways), new_ways_to_get_n[value + element])
    ways_to_get_n = new_ways_to_get_n

完成后，ways_to_get_n[0]是相当简洁的数据结构，可以与双递归一起使用以遍历包含第一个元素的所有分区。但是，这是一个挑战。这些分区中可能有0个分区。因此，当您进行两次递归操作时，请携带一个您可以到达的所有值的数据结构（相同的旧子集和技巧），并在出现0时尽早终止。 （这种簿记可能感觉上需要做很多额外的工作，但实际上可以为您节省很多。）

现在您可以通过第一个元素递归地找到最小的分区。然后递归地寻找如何对其余元素进行分区。每次执行时，您都会将其与当前的最佳状态进行比较，如果有所改进，请记录下来。

[经过各种方法分解后，就完成了。

假设整数数组（因此子集和伪多项式可能会对您有利），这将使您能够相当有效地在最小分区上进行递归。这比天真的方法更好。但这将比您想象的要大[[lot。

[我怀疑将数组的绝对值排序为第一步将使“不可约分区的过滤器”很可能在您还有很多元素的时候就从递归中分离出来，从而使该算法更加有效。