3

So I've been reading posts like Finding three elements in an array whose sum is closest to a given number and Find a pair of elements from an array whose sum equals a given number, and it appears that almost all the questions are targeted towards pairs or triplets.

My question is, given an sorted array, a number n, and a sum S, is there a "universal" algorithm that returns S by checking and adding n numbers in the array? I know how to do pairs and triplets efficiently now, but I can't seem to find any algorithm relating to n>3

Community
  • 1
  • 1
user3277633
  • 1,891
  • 6
  • 28
  • 48

1 Answers1

0

Let MAX be size of the array. Consider all binary numbers of MAX digits; let a "1" for digit j mean "the jth number is included in sum S," and a 0 for digit j mean that it isn't.

There are then 2^MAX possible solutions. You can do a linear search. Not so efficient.

You can instead do this for pruning:

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 this as exponential, but it's better.

You could now put more intelligence into this: throw out any solution in which an item > S-(n-1) (assuming all items are of size at least 1). Prefer to add things close to average of (S-(sum so far))/(items left to add).

Will have to think further if there is a better-than-exponential algorithm, or if we can prove there is not.

Topological Sort
  • 2,733
  • 2
  • 27
  • 54