java - 从一个更大的列表中找到 2 个相等和的列表

Question

好的，基本上我有一个列表或一个整数数组

列表 = (1,3,22,17,22,4,15,40)

我需要找到两个这样的列表:

列表 1 = (1,3,17,4,15,22) ... 总和 = 62

列表 2 = (22,40) ... 总和 = 62

所有整数都应该使用，整数应该在List1或List2中

----我的第一个想法----

Choose the largest nb i.e 40 and try to find integers equal to 40 and add 
to the second list ... But that's not the way ... 

上面的列表是一个示例列表……如果可能的话，我应该能够找到任何给定列表的 List1 和 List2。

Answer 1

第一步是求列表中所有元素的总和。这将始终是您要查找的两个子列表之和的两倍。使用您的示例，(1,3,22,17,22,4,15,40) 的总和为 124，是 62 的两倍。

所以现在您要在列表中寻找一组总和为 62 的数字。您不必担心找到两组(如果找到一组，其余数字的总和也肯定为 62) .我会通过算法来做到这一点——首先寻找一组大小为 1 的元素总和为 62 的集合(即，遍历列表并检查是否有任何数字为 62)。如果存在这样的数字，您就完成了。如果不是，接下来寻找大小为 2 的集合。这很棘手，因为您必须查看所有可能的组合。因为你有 7 个数字，所以有 (7*6)/2 = 21 种可能性。如果其中任何一个是 62，你就完成了。如果不是，请继续检查大小为 3 的集合。依此类推，直到达到大小 7/2(在本例中您已完成 3)。显然，对于大型集合，此过程将涉及大量计算和比较；它可以通过一些快捷方式进行优化，但基本算法是相同的。

如果最后没有找到和为 62 的子集，那是因为不存在这样的子集。