CODEWITHSUNDEEP
rubyarraysalgorithm
user3043051
user3043051

Reputation: 35

add elements of array thats sum equals the largest element

what is a way to add elements of array thats sum would equal the largest element in the array?

example for this array [4, 6, 23, 10, 1, 3] I have sorted the array first resulting in [1, 3, 4, 6, 10, 23] then I pop the last digit or the last element max = 23. I'm left with [1, 3, 4, 6, 10] and need a way to find a way to find the elements that add up to 23 which are 3 + 4 + 6 + 10 = 23. The elements don't have to be subsequent they can be at random points of the array but they must add up to max.

I can find the permutations of the sorted array from 2 elements to n-1 elements and sum them and compare them to max but that seems inefficient. plz help

Upvotes: 0

Views: 1056

Answers (1)

amit
amit

Reputation: 178421

This is exactly the subset sum problem, which is NP-Complete, but if your numbers are relatively small integers, there is an efficient pseudo-polynomial solution using Dynamic Programming:

D(i,0) = TRUE
D(0,x) = FALSE   x>0
D(i,x) = D(i-1,x) OR D(i-1,x-arr[i])

If there is a solution, you need to step back in the matrix created by the DP solution, and "record" each choice you have made along the way, to get the elements used for the summation. This thread deals with how to find the actual elements in a very similar problem (known as knapsack problem), which is solved similarly: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?

Upvotes: 1

Related Questions