Простое, но, как обычно, не самое оптимальное решение - брать каждую купюру, которая меньше общей суммы, вычитать ее из суммы, и проверять, сколько осталось. Если больше ноля - повторить с той же купюрой, или со следующей. Если 0 - мы подобрали подходящий набор купюр, складываем его в стопочку. В конце сортируем по количеству купюр.
Ну и я исходил из предположения, что у нас валидный ввод, и не будет, например, купюры достоинством в 0 или -1.
Сложность, вроде бы O(n^2) Мне кажется, что где-то должно быть более оптимальное решение, например, динамическим программированием, но я не могу его сходу придумать:
const splitMoney = (amount, available) => {
const result = [];
const getBills = (remainingAmount, currentStack, currentIndex) => {
if(!remainingAmount) {
result.push(currentStack);
return;
}
if(remainingAmount < 0 || currentIndex >= available.length) {
return;
}
for(let i = currentIndex; i<available.length; i++) {
if(available[i] <= remainingAmount) {
let billCount = 1;
while(remainingAmount >= available[i]*billCount) {
getBills(remainingAmount - available[i]*billCount, currentStack.concat(Array(billCount).fill(available[i])), i+1)
billCount+=1;
}
}
}
}
for(let i = 0; i<available.length; i++) {
if(available[i] <= amount) {
let billCount = 1;
while(amount >= available[i]*billCount) {
getBills(amount - available[i]*billCount, Array(billCount).fill(available[i]), i+1)
billCount+=1;
}
}
}
return result.sort((a, b) => a.length - b.length);
}
console.log(splitMoney(1000, [500, 200, 100]));
Как вариант, можно попробовать сначала отсортировать купюры и потом перебирать от большей к меньшей, начиная с максимального количества купюр. Тогда в конце не нужно будет сортировать и это будет потенциально быстрее.
Edit: вот похожая задача, там обсуждается несколько вариантов решения
