chooseBestSum2.js

function next_combination(a, n) {
  let k = a.length;
  for (let i = k - 1; i>= 0; --i) {
    if (a[i] < n - k + i + 1) {
      ++a[i];
      for (let j = i + 1; j < k; ++j) {
        a[j] = a[j - 1] + 1;
      }
      return true;
    }
  }
  return false;
}

function chooseBestSum2(t, k, ls) {
  let acc = [];
  for (let i = 0; i < k; i++) {
    acc.push(i);
  }
  let result = [acc.slice()];
  while (next_combination(acc, ls.length - 1)) {
    result.push(acc.slice());
  }
  
  const maxTravel = result
    .reduce((acc, item) => {
      acc.push(item.map(idx => ls[idx]).reduce((acc, item) => acc += item));
      return acc;
    }, [])
    .filter(sum => sum <= t)
    .reduce((acc, sum) => {
      if (sum > acc) {
        acc = sum;
      }
      return acc;
    }, 0);
  return (maxTravel === 0) ? null : maxTravel;
}