是否存在 K 个整数的组合，使得它们的总和等于给定数字？
我一直在为这个我被要求回答的问题而出汗（这在技术上是家庭作业）。 我考虑过使用哈希表，但我有点坚持如何使这项工作的具体细节，
问题是：
给定k组整数A1，A2，。 .,Ak 总大小为 O(n)，您应该判断是否存在 a1 ϵ A1, a2 ϵ A2,..,ak ϵ A< /em>k，这样a1+a2+..+ak−1 =ak。您的算法应在 Tk(n) 中运行 时间，其中 Tk(n) = O(nk/2 × log n) 对于偶数 k，并且 O(n(k+1)/2) 对于奇数值k。
谁能给我一个总体方向，以便我可以更接近解决这个问题？
I've been breaking a sweat over this question I've been asked to answer (it's technically homework).
I've considered a hashtable but I'm kind of stuck on the exact specifics of how I'd make this work
Here's the question:
Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist
a1 ϵ A1, a2 ϵ A2,..,ak ϵ Ak, such that a1+a2+..+ak−1 =ak. Your algorithm should run in Tk(n)
time, where Tk(n) = O(nk/2 × log n) for even k, and O(n(k+1)/2) for odd values of k.
Can anyone give me a general direction so that I can come closer to solving this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
将 k 组分为两组。对于偶数 k，两组各有 k/2 组。对于奇数 k，一组有 (k+1)/2，另一组有 (k-1)/2 组。计算每组内所有可能的总和（从每组中取出一个元素）。对于偶数 k，您将得到两个数组，每个数组都有 nk/2 元素。对于奇数 k，一个数组有 n(k+1)/2 元素，另一个数组有 n(k-1)/2 个元素。问题被简化为标准问题“给定两个数组，检查是否可以通过从每个数组中取出一个元素来达到指定的总和”。
Divide the k sets into two groups. For even k, both groups have k/2 sets each. For odd k, one group has (k+1)/2 and the other has (k-1)/2 sets. Compute all possible sums (taking one element from each set) within each group. For even k, you will get two arrays, each with nk/2 elements. For odd k, one array has n(k+1)/2 and the other array has n(k-1)/2 elements. The problem is reduced to the standard one "Given two arrays, check if a specified sum can be reached by taking one element from each array".