The JavaScript implementation selects from the array the sum equal to a fixed number of n values

  • 2020-03-30 03:49:00
  • OfStack

Real life problems may be abstracted into a data model:

Select Numbers from an array and add them to the specified value.

Most readers should have the experience of online shopping, online shopping will generally have a single function, if the reader bought 70 yuan of goods, but must be full of 100 yuan to free mail, then the system will automatically recommend some goods, add up to almost 100 yuan.

How does the system determine which items to recommend? So this is the model that we just mentioned, where we can put the prices of popular items into an array, and then we can use the algorithm to figure out which prices in the array add up to $30.

Without further ado, let's share a JavaScript version of the algorithm implementation.

Algorithm code:


function getCombBySum(array,sum,tolerance,targetCount){
var util = {

getCombination: function(arr, num) {
var r=[];
(function f(t,a,n)
{
if (n==0)
{
return r.push(t);
}
for (var i=0,l=a.length; i<=l-n; i++)
{
f(t.concat(a[i]), a.slice(i+1), n-1);
}
})([],arr,num);
return r;
},
//take array index to a array
getArrayIndex: function(array) {
var i = 0,
r = [];
for(i = 0;i<array.length;i++){
r.push(i);
}

return r;
}
},logic = {
//sort the array,then get what's we need
init: function(array,sum) {
//clone array
var _array = array.concat(),
r = [],
i = 0;
//sort by asc
_array.sort(function(a,b){
return a - b;
});
//get all number when it's less than or equal sum
for(i = 0;i<_array.length;i++){
if(_array[i]<=sum){
r.push(_array[i]);
}else{
break;
}
}

return r;
},
//important function
core: function(array,sum,arrayIndex,count,r){
var i = 0,
k = 0,
combArray = [],
_sum = 0,
_cca = [],
_cache = [];

if(count == _returnMark){
return;
}
//get current count combination
combArray = util.getCombination(arrayIndex,count);
for(i = 0;i<combArray.length;i++){
_cca = combArray[i];
_sum = 0;
_cache = [];
//calculate the sum from combination
for(k = 0;k<_cca.length;k++){
_sum += array[_cca[k]];
_cache.push(array[_cca[k]]);
}
if(Math.abs(_sum-sum) <= _tolerance){
r.push(_cache);
} 
}

logic.core(array,sum,arrayIndex,count-1,r);
}

},
r = [],
_array = [],
_targetCount = 0,
_tolerance = 0,
_returnMark = 0;

//check data
_targetCount = targetCount || _targetCount;
_tolerance = tolerance || _tolerance;

_array = logic.init(array,sum);
if(_targetCount){
_returnMark = _targetCount-1;
}

logic.core(_array,sum,util.getArrayIndex(_array),(_targetCount || _array.length),r);

return r;
}

Call description:

Array: an array of data sources. Will be selected.

Sum: sum of sums. Will be selected.

How: tolerance. If this parameter is not specified, the sum of the sum must be equal to the sum parameter, which allows the result to float within the tolerance range. Optional.

TargetCount: number of operands. If you do not specify this parameter, the result contains all possible cases. Specifying this parameter filters out the addition of a fixed number of Numbers, and if 3 is specified, the result contains only the addition of three Numbers. Optional.

Return value: returns the array array structure, the elements in the inner array are the operands, and the elements in the outer array are all possible results.


Related articles: