How to generate an addition equation for a number using only required set of numbers?

Question

I want to generate an addition equation for a random number which is look likes

5+10+2 from a set of numbers i.e [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 equation is 5.Is it possible in java script?Thanks in advance.

Answer 1

You may have multiple solutions. A dynamical programming approach could efficiently solve this;

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 <= t-n; 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 may choose the shortest one among the results set. However calculating according to a maxlen will of couse save us from calculating excess results just to be filtered out later. So the following code only works up until the maxlen is achieved.

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 <= t-n; 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 performance wise this can not be beaten easily. It takes only .190ms to get to the result [[1,2,5,10,10]].