I have a group of numbers:
const numbers = [ 4, 6, 2, 1, 5, 3, 6, 11 ]
And I would like to return these numbers in groups where the sum is closest to x. For example if x was 13, the expected output would be:
// console.log(result)
[ 2, 11 ] // sum is 13
[ 3, 4, 5 ] // sum is 12
[ 1, 6, 6 ] // sum is 13
All numbers must be used. "Closest" being below the number (not above 13), so the above example would be acceptable but if the sum was 14 it would not be. This should find the best results (closest to 13) and remove each number from the pool of options in the array when it has been grouped.
How would I approach this?
How about something like this?
const x = 13;
const result = [];
let numbers = [4, 6, 2, 1, 5, 3, 6, 11];
let i = numbers.length;
while (--i > -1) {
const length = result.length;
let target = x - numbers[i];
let a = numbers.length - 1;
while (target > 0) {
if (numbers[--a] !== target) {
if (a === -1) {
a = numbers.length - 1;
target--;
}
continue;
}
result[length] ??= [];
result[length].push(numbers[a]);
target = x - numbers[i];
for (const entry of result[length]) {
target -= entry;
}
numbers = [...numbers.slice(0, a), ...numbers.slice(a + 1)];
a = numbers.length - 1;
}
if (!result[length]) {
continue;
}
result[length].push(numbers[numbers.length - 1]);
numbers = numbers.slice(0, -1);
i = numbers.length;
}
console.log(result);
It's kinda crude though.