algorithm - 是否存在 K 个整数的组合，使得它们的和等于给定的数？

Question

我一直在为我被要求回答的这个问题(这在技术上是家庭作业)而大费周章。我已经考虑过哈希表，但我有点卡在我如何使它工作的确切细节上

问题是:

Given k sets of integers A₁,A₂,..,A_k of total size O(n), you should determine whether exist a₁ ϵ A₁, a₂ ϵ A₂,..,a_k ϵ A_k, such that a₁+a₂+..+a_k−1 =a_k. Your algorithm should run in T_k(n) time, where T_k(n) = O(n^k/2 × log n) for even k, and O(n^(k+1)/2) for odd values of k.

任何人都可以给我一个大体方向，以便我可以更接近解决这个问题吗？

Answer 1

将k组分成两组。对于偶数 k，两组各有 k/2 组。对于奇数 k，一组有 (k+1)/2 组，另一组有 (k-1)/2 组。计算每组内所有可能的总和(从每组中取一个元素)。对于偶数 k，您将得到两个数组，每个数组都有 n^k/2 个元素。对于奇数 k，一个数组有 n^(k+1)/2，另一个数组有 n^(k-1)/2 个元素。问题简化为标准问题“给定两个数组，检查是否可以通过从每个数组中取一个元素来达到指定的总和”。