Executando verificação de segurança...
2

Só um detalhe, teste o seu código com:

const availableNotes = {
    20: 4,
    50: 3,
    100: 5
};
const value = 60;

O seu código vai retornar notes: [50]. Ou seja, apenas uma nota de 50. Mas isso não é suficiente para dar o valor (60), pois o correto seria retornar 3 notas de 20.

E se testar com:

const availableNotes = {
    20: 2
};
const value = 60;

Vai retornar:

{
  notes: [ 20, 20, 20 ],
  availableNotes: { '20': -1 },
  availableNotesSum: -20
}

Isso porque faltou verificar se a quantidade não zerou.


Para arrumar isso, temos que modificar um pouco o código. Primeiro temos que testar com todas as notas, e se não der, testamos sem uma das notas (por exemplo, sem as notas de 100). Se não der, testamos sem as notas de 50 e assim por diante, até encontrar uma combinação que dê certo. Se todas as combinações falharem, é porque não é possível.

Ficaria assim:

// gera todas as combinações do array
function *subsets(array, offset = 0, minSize = 0) {
    while (offset < array.length) {
        let first = array[offset++];
        for (let subset of subsets(array, offset)) {
            subset.splice(0, 0, first);
            if (subset.length >= minSize)
                yield subset;
        }
    }
    if (minSize === 0)
        yield[];
}

function cashWithdrawal(value, availableNotes) {
    let notes = [];
    let availableNotesOriginal = structuredClone(availableNotes);
    // array com os valores de todas as notas disponíveis
    const allNotesValues = Object.keys(availableNotes).map((note) => Number(note)).sort((a, b) => b - a);
    for (const subsetNotes of subsets(allNotesValues, 0, 2)) {
        let remainingValue = value;
        for (const noteValue of subsetNotes) {
            while (remainingValue >= noteValue && availableNotes[noteValue] > 0) {
                notes.push(noteValue);
                remainingValue -= noteValue;
                availableNotes[noteValue]--;
            }
        }
        if (remainingValue == 0) { // se o valor zerou, é porque deu certo
            const availableNotesSum = Object.entries(availableNotes).reduce((sum, [note, quantity]) => sum + Number(note) * quantity, 0);
            return {
                notes,
                availableNotes,
                availableNotesSum
            };
        } else {
            // se não deu certo, zera o array de notas e volta para as notas disponíveis original
            notes = [];
            availableNotes = JSON.parse(JSON.stringify(availableNotesOriginal));
        }
        // se o valor não zerou, é porque não foi possível, então tenta com a próxima combinação de notas
    }
    return null; // se tentou todas as combinações e chegou aqui, é porque não é possível
}
let availableNotes = {
    20: 4,
    50: 3,
    100: 5
};
let value = 60;

console.log(cashWithdrawal(value, availableNotes));

Resultado (3 notas de 20):

{
  notes: [ 20, 20, 20 ],
  availableNotes: { '20': 1, '50': 3, '100': 5 },
  availableNotesSum: 670
}

Se eu mudar o valor para 75, a função retorna null, pois não é possível obter o valor desejado com as notas disponíveis. E se testar com availableNotes = { 20: 2 }; e value = 60;, também vai retornar null, pois também não é possível atingir o valor.


A função subsets é uma generator function, que em vez de retornar todas as combinações de uma vez, ela "retorna" apenas uma de cada vez (isso economiza memória, pois dependendo da quantidade de notas, a quantidade de combinações possíveis pode ficar muito grande).

Como eu faço um loop pelos subsets e verifico um por um (e retorno se encontrar um que deu certo), isso faz com que o código consuma menos memória, pois eu trabalho apenas com uma combinação por vez, e em seguida a descarto para ir para a próxima.

Eu também clono o availableNotes com structuredClone porque se uma combinação não der certo, preciso restaurar os valores originais. Mas vc também pode trocar por JSON.parse(JSON.stringify(availableNotes)).

Carregando publicação patrocinada...
1
1

E outra coisa, não precisa do while para ficar subtraindo uma nota de cada vez. Vc pode ver quantas notas precisa, e subtrair tudo de uma vez:

function cashWithdrawal(value, availableNotes) {
    let notes = [];
    let availableNotesOriginal = structuredClone(availableNotes);
    // array com os valores de todas as notas disponíveis
    const allNotesValues = Object.keys(availableNotes).map((note) => Number(note)).sort((a, b) => b - a);
    for (const subsetNotes of subsets(allNotesValues, 0, 2)) {
        let remainingValue = value;
        for (const noteValue of subsetNotes) {
            // quantas notas desse valor eu preciso?
            const need = Math.min(Math.floor(remainingValue / noteValue), availableNotes[noteValue]);
            for (let i = 0; i < need; i++) { // adiciona as notas
                notes.push(noteValue);
            }
            // subtrai a quantidade e atualiza o valor restante
            availableNotes[noteValue] -= need;
            remainingValue -= noteValue * need;
        }
        if (remainingValue == 0) { // se o valor zerou, é porque deu certo
            const availableNotesSum = Object.entries(availableNotes).reduce((sum, [note, quantity]) => sum + Number(note) * quantity, 0);
            return {
                notes,
                availableNotes,
                availableNotesSum
            };
        } else {
            // se não deu certo, zera o array de notas e volta para as notas disponíveis original
            notes = [];
            availableNotes = JSON.parse(JSON.stringify(availableNotesOriginal));
        }
        // se o valor não zerou, é porque não foi possível, então tenta com a próxima combinação de notas
    }
    return null; // se tentou todas as combinações e chegou aqui, é porque não é possível
}

Ou seja, basta dividir o valor restante pelo valor da nota para saber quantas eu preciso. Mas se não tiver notas suficientes, eu pego tudo que tem disponível e continuo com a próxima nota.

E faço isso até acabar as notas, e vejo se o valor restante é zero, para saber se deu certo.

1