ClosestSum

by khrome

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/mootools/1.4.5/mootools-core-full-compat.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mootools-more/1.4.0.1/mootools-more-yui-compressed.js"></script>

JavaScript

var stuff = [
    330,
    2157,
    483,
    320,
    52476.2,
    2200,
    13980.52,
    327,
    927.93,
    11147.27,
    35376.54,
    4500,
    2500,
    54750,
    1250,
    4000,
    1500,
    2157,
    483
];

Array.implement({
    sum : function(){
        var val = 0;
        this.each(function(item){
            val += item;
        });
        return val;
    }
})
var closest = Number.MAX_VALUE;
var closestStack = [];
var bruteRecursive = function(target, nums, stack){
    if(!stack) stack = [];
    var currentSum = stack?stack.sum():0;
    if(nums.length === 0) return;
    nums.each(function(num){
        var newArray = nums.clone();
        var newStack = stack.clone();
        var candidate = currentSum+num;
        newArray.erase(num);
        newStack.push(num);
        var distance = Math.abs(target - closest);
        if(distance > Math.abs(target - candidate)){
            closest = candidate;
            closestStack = newStack;
        }
        if(candidate === target) console.log(newStack);
        if(candidate > target) return;
        bruteRecursive(target, newArray, newStack);
    });
};
bruteRecursive(3289, stuff);
document.write('closest('+closest +') : '+closestStack);