Getting three numbers from set that combined gives n

Question

I have run into a little problem that I have been pondering about, and can't figure out a good solution for. Let's say that I have a set of numbers like this one:

[1, 2, 3, 4, 6, 9, 8, 12, 5, 10, 15, 18, 7, 14, 21, 16, 24, 27, 20, 30, 11, 22,25, 33, 36, 13, 26, 39, 28, 42, 45, 32, 48, 50]

I then get a number n, which might be "90", and then I need to output three numbers from the set that add up to n. so for n = 90 that could be 50, 39 and 1.

But do I most effeciently compute this, but also be able to compute whether such three numbers a producible?

I first thought that I could just do a naive greedy approach where I would just pick the biggest number that is at least two smaller than n, and then combine it with whatever values needed to fill in the gap.

This approach however might fail in a case where the set is [22,7,8,10] and n=25 where my naive approach would pick 22 as the first number, and then not be able to use the other numbers to fill it out. It also is not able to identfy the case where it is impossible to get n with three numbers from your set, without trying all combinations.

I then thought a bit about making a dynamic programming solution. But I can't figure out whether i'm overcomplicating the problem, or how this dp solution should look.

Does someone have some good tips?

Answer 1

Quite simple in O(m^2). Sort items in ascending order x1 to x-mal. Repeat for k = m, m-1, …, 3 as long as xk + x(k-1) + x(k-2) >= n.

For each k set I=1, j=k-1. As long as i +1< j and xi + xj +xk > n increase i by 1. As long as j-1 > i and xi + xj + xk > n decrease j by 1. If the sum matches we found the solution. Repeat as long as i < j-1, then take the next k.

Answer 2

Let k’ = k or k’ = k-1. Given is an array of n integers and an integer m. We can find (k+k’) array elements that add up to m in O(n^k) time and O(n^k’) space:

Create a hash table containing all sums of k’ different array elements, together with a list of those elements.

For each sum s of k different items, lookup n-s in the hash table. If found and the array elements are different we have a solution.