Best K Combos, probably

kcombos.js

const pq = [];

function enqueue(value, priority) {
  const item = { value, priority };
  for (let i = 0; i < pq.length; i++) {
    const { value: pqValue, priority: pqPriority } = pq[i];
    // Maintain min-heap, sorted by (value, priority)
    if (value < pqValue || (value === pqValue && priority < pqPriority)) {
      pq.splice(i, 0, item);
      return;
    }
  }

  // Splice can't append, push if item has highest value & priority
  pq.push(item);
}

function dequeue() {
  return pq.shift();
}

function main(inputs, k) {
  // Sum every positive value to get the combo other combos are based on
  const bestCombo = inputs.reduce((sum, cur) => (cur > 0 ? sum + cur : sum), 0);

  // Get the absolute value of each input
  // Each value now represents removing a popular item or adding an unpopular item
  absInputs = inputs.map((i) => Math.abs(i));
  absInputs.sort();

  // The best combo is always the first result
  result = [bestCombo];

  // Add the smallest popularity value to the queue for consideration
  enqueue(absInputs[0], 0);

  // Generate combinations to be subtracted from the best combination until `k` combinations have been gathered
  while (result.length < k) {
    // The next queue item represents the smallest possible penalty to create a new combination from the overall best
    const { value, priority: i } = dequeue();
    result.push(bestCombo - value);

    // Add two combos to the queue for consideration
    // One combo will contain the current value
    // Both combos will contain the next value
    // Examines all combinations in ideal order
    if (i + 1 < absInputs.length) {
      enqueue(value - absInputs[i] + absInputs[i + 1], i + 1);
      enqueue(value + absInputs[i + 1], i + 1);
    }
  }

  return result;
}

const inputs = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, -1, -1, -1];
const k = 100;

console.log(main(inputs, k));