在数组中找到总和等于给定值的最小元素

Question

我试图找出数组中的总和等于给定输入的最小元素。我尝试了很少的输入总和，但在第一种情况下只能找到一对，而我需要实现的不仅仅是一对。

var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b) {
  return a - b;
});
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize) {

  if (arr[l] + arr[arrSize] === sum) {
    var result = newArr.concat(arr[l], arr[arrSize]);
    console.log(result);
    break;
  } else if (arr[l] + arr[arrSize] > sum) {
    arrSize--;
  } else {
    l++;
  }
}

输入数组：[10，0，-1，20，25，30]

必填项：45

输出：[20、25]

我正在努力

所需总和：59

输出：[10，-1、20、30]

Answer 1

一种选择是找到数组的所有可能的子集，然后通过总和为所需值的子集来过滤它们，然后识别长度最小的子集：

const getMinElementsWhichSum = (arr, target) => {
  const subsets = getAllSubsetsOfArr(arr);
  const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
  return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, { length: Infinity });
};
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

// https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
function getAllSubsetsOfArr(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}