我正在做一些算法练习并遇到了这个。
我有一个列表/数组，如下所示:[1, 5, 4, 9, 10, 2, ...]
我将如何返回查找具有相同总和的唯一列表集？例如，(5, 4) 等于 (9)，(1, 5) 等于 6，依此类推。
我熟悉查找列表中的所有集合，但附加的技巧是这些集合必须是唯一的，就像一个索引用于一个集合，相同的索引不能用于另一个集合.
有什么想法吗？谢谢。
编辑:
经过进一步思考，这就是我的想法。我列出了所有可能的集合，而不担心唯一性。然后我得到原始超集数组的最小值和最大值。我从最小值到最大值循环遍历值，递增 1 并检查每组。创建一个 HashMap 。如果该集合的总和等于我们正在检查的值，我们将该集合添加到列表中。此外，如果集合的索引的值有键，我们将 HashMap 中与键相关的值设置为 True。继续使用 HashMap 条件检查每个集合。然后我们返回应该只包含唯一集的列表列表。
有道理吗？
最佳答案
列出所有可能的集合 - 这在时间和空间上当然是指数级的。这是一个多项式时间解决方案(如果我理解这个问题):
- 迭代列表，保留两个指针 - 每次第一个指针递增时，第二个指针都会从该索引+1运行到列表末尾。
- 对于两个元素的每个组合，如果它们的总和低于所需的总和，则它们的组合值将被插入列表的末尾(保留组成它的原始索引)。
- 一旦找到恰好等于总和的元素组合，相应索引中的所有元素都会从列表中移出，并将该集合插入到不相交集合的解向量中。
在此迭代过程结束时，您将获得一整套不相交的集合 - 不一定是具有最多元素数或最多组数的集合，而是无法从剩余元素创建其他集合的集合在列表中。
关于arrays - 列表中唯一的集合总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21965519/