CODEWITHSUNDEEP
algorithmruntime
Hamza Khan
Hamza Khan

Reputation: 131

How can I find elements in an integer array that add up to K?

Given an array of integers and a number k. Find a combination of elements in the array that add up to k. Recently I got a coding question where I was given an array of positive integers A and k.

Let A = {4, 15, 7, 21, 2} and k = 13 and my algorithm was supposed to return a list of indexes of the elements that add up to k. In this case: [0,2,4]. Each element can only be used once.

How would I go about approaching this problem? Also what would be the time and space complexity.

Upvotes: 0

Views: 913

Answers (1)

olegarch
olegarch

Reputation: 3891

This is dynamic programming solution for this problem, and I coded it for Emercoin, within transaction optimizer.

Idea of algorithm: You create array of [k+1] element. Index in this array is sum, which can be reached by some input value, and value withing array - number of input, used for reach this sum. Value -1 shows, this sum cannot be reached by current subset of elements.

Lets see your example. In your example, k=13, and we initially create array DP from 14 of -1:

DP = (-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

empty output set (sum = 0) can be reached in any way, and because of it, we deposit into DP[0] some non-minus_1, for example - 0. as result, DP[0] == 0:

DP = ( 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

Thereafter, for all input values from your array A[i], do following:

  • iterate array DP in backward
  • if DP[j] >= 0 && DP[j + A[i]] < 0 then DP[j + A[i]] = i;

There is idea: if sum "j" was reached in some previous step, and we have value A[i], then sum "j+A[i]" can be reached, by adding i-th element from the array A.

In our example, after adding your A[0]==4, we will have DP:

DP = ( 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1)

This zero is meaning: sum "4" can be reached by A[0].

Trying to add A[1] = 15. There is two possible location for i=1, DP[19] and dp[15]. Both out of array bound, so we just don't update DP array.

Trying to add A[2] = 7. There is two possible location for i=2, DP[11] and dp[7]. After update, DP array will be:

DP = ( 0 -1 -1 -1 0 -1 -1 2 -1 -1 -1 2 -1 -1)

Skip A[3] == 21, as same as A[1].

Trying to add A[4] = 2. DP-array would be:

DP = ( 0 -1 4 -1 0 -1 4 2 -1 4 -1 2 -1 4)

Input array A[] exhaust, DP array is ready for interpretation. We see, DP[13] >= 0, so sum 13 is reached. DP[13] == 4, so sum "13" is reached by A[4]. Remember it. Consider DP-array as linked list, where value referred to previous position. So, prev = 13-2 = 11. We see, A[2] also included into the sum. remember "2". Prev position: prev = 11-7 = 4. See DP[4]. there is "0". remember [0], too. Prev = 4-4 = 0. We reached DP[0], stop interpretation. Thus, we collected remembered indexes in A[4,2,0].

Problem solved.

Upvotes: 2

Related Questions