Is there a combination of K integers, so that their sum is equal to the given number?

Question

I was breaking a sweat over this question. I was asked to answer (this is technically homework). I looked at the hash table, but I'm kind of fixated on the exact specifics of how I will do this work.

Here's the question:

For k sets of integers A ₁ , A ₂ , .., A _{k of} total size O (n), you must determine if a ₁ ε A ₁ , a ₂ ε A ₂ , .., a _k ε A _k , so a ₁ + a ₂ + .. + a _{k & minus; 1} = a <sub> xub>. Your algorithm should work at T _k (n) time, where T _k (n) = O (n ^{k / 2} x log n) for even k and O (n ^{(k + 1) / 2} ) for odd k .

Can someone give me a general direction so that I can come closer to solving it?

Answer 1

Divide 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. Calculate all possible amounts (taking one element from each set) within each group. For even k you get two arrays, each of which contains n ^{k / 2} . For odd k, one array has n ^{(k + 1) / 2} and the other array has n ^{(k-1) / 2} elements. The problem boils down to the standard one: "Given two arrays, check whether it is possible to achieve the indicated amount by taking one element from each array."