Q: Sum of numbers with approximation and no repetition For an app I'm working on, I need to process an array of numbers and return a new array such that the sum of the elements are as close as possible to a target sum. This is similar to the coin-counting problem, with two differences: 


*

*Each element of the new array has to come from the input array (i.e. no repetition/duplication)

*The algorithm should stop when it finds an array whose sum falls within X of the target number (e.g., given [10, 12, 15, 23, 26], a target of 35, and a sigma of 5, a result of [10, 12, 15] (sum 37) is OK but a result of [15, 26] (sum 41) is not.


I was considering the following algorithm (in pseudocode) but I doubt that this is the best way to do it.
function (array, goal, sigma)
    var A = []
    for each element E in array
        if (E + (sum of rest of A) < goal +/- sigma)
            A.push(E)
    return A

For what it's worth, the language I'm using is Javascript. Any advice is much appreciated!

A: This is not intended as the best answer possible, just maybe something that will work well enough. All remarks/input is welcome.
Also, this is taking into mind the answers from the comments, that the input is length of songs (usually 100 - 600), the length of the input array is between 5 to 50 and the goal is anywhere between 100 to 7200.
The idea: 


*

*Start with finding the average value of the input, and then work out a guess on the number of input values you're going to need. Lets say that comes out x.  

*Order your input.  

*Take the first x-1 values and substitute the smallest one with the any other to get to your goal (somewhere in the range). If none exist, find a number so you're still lower than the goal.  

*Repeat step #3 using backtracking or something like that. Maybe limit the number of trials you're gonna spend there.

*x++ and go back to step #3. 


A: I would use some kind of divide and conquer and a recursive implementation. Here is a prototype in Smalltalk
SequenceableCollection>>subsetOfSum: s plusOrMinus: d
    "check if a singleton matches"
    self do: [:v | (v between: s - d and: s + d) ifTrue: [^{v}]].

    "nope, engage recursion with a smaller collection"
    self keysAndValuesDo: [:i :v |
        | sub |
        sub := (self copyWithoutIndex: i) subsetOfSum: s-v plusOrMinus: d.
        sub isNil ifFalse: [^sub copyWith: v]].

    "none found"
    ^nil

Using like this:
#(10 12 15 23 26) subsetOfSum: 62 plusOrMinus: 3.

gives:
#(23 15 12 10)


A: Here's one commented algorithm in JavaScript:
var arr = [9, 12, 20, 23, 26];
var target = 35;
var sigma = 5;
var n = arr.length;

// sort the numbers in ascending order
arr.sort(function(a,b){return a-b;});

// initialize the recursion
var stack = [[0,0,[]]];

while (stack[0] !== undefined){
  var params = stack.pop();
  var i = params[0]; // index
  var s = params[1]; // sum so far
  var r = params[2]; // accumulating list of numbers

  // if the sum is within range, output sum
  if (s >= target - sigma && s <= target + sigma){
    console.log(r);
    break;

  // since the numbers are sorted, if the current
  // number makes the sum too large, abandon this thread
  } else if (s + arr[i] > target + sigma){
    continue;
  }

  // there are still enough numbers left to skip this one
  if (i < n - 1){ 
    stack.push([i + 1,s,r]);
  }

  // there are still enough numbers left to add this one
  if (i < n){
    _r = r.slice();
    _r.push(arr[i]);
    stack.push([i + 1,s + arr[i],_r]);
  }
}

/* [9,23] */


A: With limited input this problem is good candidate for dynamic programming with time complexity O((Sum + Sigma) * ArrayLength)
Delphi code:
  function FindCombination(const A: array of Integer; Sum, Sigma: Integer): string;
  var
    Sums: array of Integer;
    Value, idx: Integer;
  begin
    Result := '';
    SetLength(Sums, Sum + Sigma + 1); //zero-initialized array
    Sums[0] := 1; //just non-zero

    for Value in A do begin
      idx := Sum + Sigma;
      while idx >= Value do begin
        if Sums[idx - Value] <> 0 then begin //(idx-Value) sum can be formed from array]

          Sums[idx] := Value;    //value is included in this sum

          if idx >= Sum - Sigma then begin  //bingo!
            while idx > 0 do begin  //unwind and extract all values for this sum
              Result := Result + IntToStr(Sums[idx]) + ' ';
              idx := idx - Sums[idx];
            end;
            Exit;
          end;

        end;
        Dec(idx); //idx--
      end;
    end;
  end;

