The most efficient algorithm for finding a subset of a sorted array that has a given sum
So, I've read posts like Finding three elements in an array whose sum is closest to a specified number and Find a pair of elements from an array whose sum is a given number , and it seems that almost all of the questions target pairs or triplets.
My question, given a sorted array, number n, and sum S , is there a "generic" algorithm that returns S by checking and adding n numbers in the array? I know how to efficiently do pairs and triplets now, but I cannot find an algorithm relating to n> 3
source to share
Let MAX be the size of the array. Consider all binary MAX digits; let "1" for digit j mean "j-th number is included in the sum of S", and 0 for digit j means that it is not.
There are then 2 ^ MAX possible solutions. You can perform a linear search. Not as effective.
Instead, you can do this to trim:
findSolution (Array, MAX, n, S, SolutionSoFar, j) is
if SolutionSoFar has n digits set to 1
if the sum it represents == S
return SolutionSoFar -- we win
else
return false
if (result = findSolution (Array, MAX, n, S, SolutionSoFar with jth set to 1, j+1))
return result
else if (result = findSolution (Array, MAX, n, S, SolutionSoFar with jth set to 0, j+1))
return result
else
return false
findSolution (Array, MAX, n, S, a binary number of MAX digits all 0's, 0)
O-notation will still show it as exponential, but better.
Now you can add more information: throw away any solution where item> S- (n-1) (assuming all items are at least 1 in size). Prefer to add things close to the mean (S- (sum so far)) / (items to add).
We will have to think further if there is an algorithm better than exponential, or if we can prove that there is none.
source to share