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

Question

我一直在为这个我被要求回答的问题（从技术上讲是家庭作业）而汗流浃背。我考虑过一个哈希表，但我有点坚持我如何使这项工作的确切细节

这是问题：

给定k组整数A ₁ , A ₂ ,.., A _k的总大小为 O( n )，您应该确定是否存在 a ₁ ϵ A ₁ , a ₂ ϵ A ₂ ,.., a _k ϵ A _k ,使得a ₁ + a ₂ +..+ a _{k -1} = a _k。您的算法应该在 T _k ( n ) 时间内运行，其中 T _k( n ) = O( n ^{k /2} × log n ) 对于偶数k， O( n ^{( k +1)/2} ) 对于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 个}元素。问题简化为标准问题“给定两个数组，检查是否可以通过从每个数组中获取一个元素来达到指定的总和”。