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

1 answer

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
       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
     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.



All Articles