1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Have you considered the naive solution consisting of checking all the possible triples in the array? This is obviously in $\mathcal{O}(p^3)$ (where $p$ is the size of the array). This is not optimal, but it is simple and it works. $\endgroup$
    – Nathaniel
    Nov 13, 2021 at 18:57
  • $\begingroup$ yes, I did think of this, but as far as I am informed, it should be able to be solved in better than linear time $\endgroup$ Nov 13, 2021 at 19:05
  • 1
    $\begingroup$ en.wikipedia.org/wiki/3SUM $\endgroup$ Nov 14, 2021 at 6:56
  • $\begingroup$ Is combined restricted to sum? $\endgroup$
    – greybeard
    Nov 14, 2021 at 7:00
  • $\begingroup$ yes combined can only be sum, or maybe i'm misunderstanding the question $\endgroup$ Nov 14, 2021 at 12:54

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.