Best K Combos, probably

kcombos.js

const values = [5, 4, 4, 4, 4, 0, 0, 0, -1, -1, -1, -3];
const k = 20;

function main() {
  // Build a lookup of value frequencies, and calculate the best combo
  let bestCombo = 0;
  const frequencies = {};
  for (const value of values) {
    const absValue = Math.abs(value);
    if (!frequencies[absValue]) {
      frequencies[absValue] = 1;
    } else {
      frequencies[absValue] += 1;
    }
    if (value > 0) {
      bestCombo += value;
    }
  }

  // For each value, calculate its ratio with the next highest value
  // This determines the maximum size of combinations we should examine before moving to a higher value
  const distinctValues = Object.keys(frequencies);
  const ratios = [];
  for (let i = 0; i < distinctValues.length - 1; i++) {
    const [value, nextValue] = [distinctValues[i], distinctValues[i + 1]];
    const frequency = frequencies[value];

    // Use every possible combination of zero values
    let ratio = frequency;
    if (value !== 0) {
      const maxRatio = Math.floor(nextValue / value);
      ratio = Math.min(maxRatio, frequency);
    }

    ratios.push(ratio);
  }

  const result = [bestCombo];

  for (let i = 0; i < distinctValues.length; i++) {
    const value = distinctValues[i];
    const frequency = frequencies[value];
    const ratio = ratios[i] || 1;
    for (let r = 1; r <= ratio; r++) {
      const comboCount = getCombinationsForChoice(frequency, r);
      for (let j = 0; j < comboCount; j++) {
        result.push(bestCombo - (r * value));
        if (result.length === k) {
          return result;
        }
      }
    }
  }
}

function getCombinationsForChoice(n, r) {
  if (r === 1) {
    return n;
  }
  return factorial(n) / (factorial(r) * factorial(n - r));
}

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(main());