Find the indices of those elements that will be equal to x after adding their values

Question

So, I have an array that looks something like this:

var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];

My question is how can I find the indices of those elements that will be equal to the number xafter adding their values. In this case, the refund will be:

[1, 3, 3, 3]

Of course, this can also be done with [0, 0, 0, 1, 2]or [0, 0, 0, 0, 2, 2, 2], but a lower length of the returned array will be better.

Answer 1

There are more effective ways to do this, but this is a very obvious / clean solution. We will consider this as a linear equation, where it combocontains coefficients for each value in arr:

// your initial x and arr
var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];

// maximums[i] is the maximum amount of arr[i] you can ever
// have in any combination
var maximums = arr.map(function(item){ return Math.floor(x / item.value) });

// an array of the current coefficients we're trying. combo[i]
// corresponds to the coefficient for arr[i]
// we will start off with all coefficients set to 0 and
// increase each one by 1 as we go along
var combo = arr.map(function(){ return 0 });

// the sum we get with the current coefficients
var sum = 0;

// take the current coefficients in combo and try the next
// coefficient from left-to-right, we know when to stop
// trying to increase a given coefficient when it exceeds
// its corresponding value in the maximums array
function next() {
  for(var i = 0; i < combo.length; i++) {
    combo[i]++;
    // we increased the coeff. so increase the sum
    sum += arr[i].value;
    if(combo[i] <= maximums[i]) {
      // the coefficient is smaller/equal to its max size, so we're done
      break;
    }else{
      // we've maxed out the right most coeff. so bail
      if(i == combo.length-1) return false;
      // reset this coefficient, remove it from sum & cont. loop
      sum -= arr[i].value * combo[i];
      combo[i] = 0;
    }
  }
  return true;
}

// now we just enumerate all combinations until the sum equals x
while(next()) {
  if(sum == x) break;
}

// if no combination is found, abort
if(sum != x) {
  console.log('not possible');

// otherwise print the combination that works
}else{
  for(var i = 0; i < combo.length; i++) {
    if(combo[i] == 0) continue;
    console.log(combo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
  }
}

, :

function coeffsUsed() {
  var count = 0;
  for(var i = 0; i < combo.length; i++) {
    if(combo[i] > 0) count++;
  }
  return count;
}

// now we just enumerate all combinations until the sum equals x
var smallestCombo = {};
var smallest = -1;
while(next()) {
  if(sum == x) {
    var count = coeffsUsed();
    if(smallest == -1 || count < smallest) {
      smallest = count;
      smallestCombo = combo.slice(0); // clones the array
    }
  } 
}

// if no combination is found, abort
if(smallest == -1) {
  console.log('not possible');

// otherwise print the combination that works
}else{
  for(var i = 0; i < smallestCombo.length; i++) {
    if(smallestCombo[i] == 0) continue;
    console.log(smallestCombo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
  }
}