Real-life problems may be abstracted into such a data model:
Pick out several numbers from an array and let the sum of these numbers be the specified value.
Most readers should have had online shopping experience. Online shopping generally has a order-making function. If the reader buys a product worth 70 yuan, but must be over 100 yuan to ship free shipping, the system will automatically recommend some products, which will add up to 100 yuan.
How does the system determine which products to recommend? This is actually the model mentioned just now. We can put the prices of hot-selling products into an array, and then use the algorithm to find out which price sums in the array are 30 yuan.
Less nonsense, Xiaocai will share with you a JavaScript version of algorithm implementation.
Algorithm code:
function getCombBySum(array,sum,tolerance,targetCount){var util = {/*get combination from arrayarr: target arraynum: combination item lengthreturn: one array that contains combination arrays*/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<=ln; i++){f(t.concat(a[i]), a.slice(i+1), n-1);}})([],arr,num);return r;},//take array index to a arraygetArrayIndex: 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 needinit: function(array,sum) {//clone arrayvar _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 sumfor(i = 0;i<_array.length;i++){if(_array[i]<=sum){r.push(_array[i]);}else{break;}}return r;},//important functioncore: function(array,sum,arrayIndex,count,r){var i = 0,k = 0,combArray = [],_sum = 0,_cca = [],_cache = [];if(count == _returnMark){return;}//get current count combinationcombArray = util.getCombination(arrayIndex,count);for(i = 0;i<combArray.length;i++){_cca = combArray[i];_sum = 0;_cache = [];//calculate the sum from combinationfor(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 instructions:
array: Data source array. Required.
sum: sum of sum. Required.
tolerance: Tolerance. If this parameter is not specified, the sum of the sum must be equal to the sum parameter, specifying this parameter will cause the result to float within the tolerance range. Optional.
targetCount: Number of operands. If this parameter is not specified, the result contains all possible cases. Specifying this parameter can filter out a fixed number of numbers and add them. If specified as 3, the result contains only three numbers. Optional.
Return value: The returned array structure is an array, the elements in the inner array are operands, and the elements in the outer array are all possible results.