arrays - 检查是否可以将数组划分为总和至少 k 的 2 个子集？

Question

给定一个大小为 n 的数组，我们必须检查是否可以将 Array 的元素分成两个子集，使得两个子集的总和至少为 k。
我该如何解决这个问题？

我的方法：

我想到了一种贪婪的方法来获取所有较大的元素，直到它达到 k 并检查 if total_sum-sum>=k。但是这个逻辑是不正确的。

我认为的另一种方法是蛮力，简单地递归所有可能的子集并找出它是否满足我的条件。但它的时间复杂度是指数级的，即使在使用 DP 之后O(n^2)

但是2<=n<=2*10^5。

你能帮我找到解决这个问题的最佳方法吗？

标签： arraysalgorithmsortingoptimization

Answer 1

这是不可能的

如果我们取k整个数组之和的一半，则该问题称为分区问题，即著名的NP 完全问题。没有已知算法可以始终如一地（在合理的时间内）解决 的任何NP 完全问题n=2*10^5。

PS请注意，蛮力解决方案会运行O(2^n)，而不是O(n^2)。