How to generate the addition equation for a number using only the necessary set of numbers?

Question

I want to generate an addition equation for a random number that looks like

5 + 10 + 2 from the set of numbers ie [1,2,5,10,50].

var randomNumber = Math.floor(Math.random() * (10 - 1 + 1)) + 1; var setOfNums = [1,2,5,10,50]; var additionEquation; //ex: for randomNumber = 28; additionEquation = 10+10+5+2+1; 

And the maximum number of elements in the equation is 5. Is this possible in a java script? Thanks in advance.

Answer 1

You may have several solutions. A dynamic programming approach could effectively solve this problem,

 function getCombos(a,t){ var h = {}, len = a.length, n = 0; for (var i = 0; i < len; i++){ n = a[i]; h[n] ? h[n].push([n]) : h[n] = [[n]]; for(var j = a[0]; j <= tn; j++){ h[j] && (h[j+n] = h[j+n] ? h[j+n].concat(h[j].map(s => s.concat(n))) : h[j].map(s => s.concat(n))); } } return h[t] || []; } var arr = [1,2,5,10,50], target = 28, result = []; console.time("combos"); result = getCombos(arr,target); console.timeEnd("combos"); console.log(`${result.length} solutions found`); console.log(JSON.stringify(result)); 

Then you can choose the shortest among the result set. However, computing according to a maxlen will couse will save us from calculating redundant results that will be filtered out later. Thus, the following code only works until reaching maxlen .

 function getCombos(a,t,l){ var h = {}, len = a.length, n = 0; for (var i = 0; i < len; i++){ n = a[i]; h[n] ? h[n].push([n]) : h[n] = [[n]]; for(var j = a[0]; j <= tn; j++){ h[j] && (h[j+n] = h[j+n] ? h[j+n].concat(h[j].reduce((r,s) => s.length < l ? (r.push(s.concat(n)),r) : r, [])) : h[j].reduce((r,s) => s.length < l ? (r.push(s.concat(n)),r) : r, [])); } } return h[t] || []; } var arr = [1,2,5,10,50], target = 28, maxlen = 5, result = []; console.time("combos"); result = getCombos(arr,target,maxlen); console.timeEnd("combos"); console.log(result.length) console.log(JSON.stringify(result)); 

I believe that wise performance cannot be easily beaten. Only 0.17 ms is required to achieve the result [[1,2,5,10,10]] .

Answer 2

This problem can be solved with recursive combinations of all possible sums , until we reach the goal. .

One solution contains maximum 5 as the length, where 5 is the length of the setOfNums array.

 var randomNumber = Math.floor(Math.random() * 30) + 1; console.log(randomNumber); var setOfNums = [1,2,5,10,50]; setOfNums=setOfNums.sort(function(a,b){ return ba; }); subset_sum(setOfNums,randomNumber); function subset_sum(numbers, target, partial){ partial = partial || []; s = partial.reduce(function(contor,elem){ return contor+elem; },0); if(s == target){ partial=partial.sort(function(a,b){ return ab; }); console.log("sum"+JSON.stringify(partial)+"="+ target); } if(s >= target) return; if(partial.length>numbers.length) return; numbers.forEach(function(number,index){ n = numbers[index]; subset_sum(numbers, target, partial.concat(n)); }); }