Does a combination of K integers exist, so that their sum is equal to a given number?

Question

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 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.

Can anyone give me a general direction so that I can come closer to solving this?

Charcot

congratulations on admitting homework. Do you have any answer to the problem (disregarding complexity)? If so, what do you analyze it's complexity as? Do you think your approach is completely wrong-headed, or are there specific parts that you think are faulty? – Cordalia

The only thing I could figure out that would work 100% was the most naive implementation of n^n (ie. checking ALL the options). Obviously this is not the right way to go :( – Charcot

I wonder if this would be better suited to Math Overflow? – Loring

Answer 1

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 n^k/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".

Phionna

Thanks for your answer! This seems right intuitively, but I can't completely figure out how this actually reduced the problem. Can you elaborate a tiny bit? – Charcot

Given two arrays of size O(n) each, you can find if a sum exists in O(n*log n). The solution is not too difficult. I would feel guilty if I give it out to you since you have mentioned it is a homework! – Phionna

@viswanathgs: you can even solve the two arrays problem in O(n) time on average. – Engud

@unforgiven: That is only if the arrays are sorted, right? Or is there something I'm not looking at? – Phionna