Comments 1
Дальше жадный алгоритм: берём самого большого должника и самого большого кредитора, закрываем меньшую из двух сумм, повторяем.
Не обязательно брать максимальных. Общее количество переводов почти всегда равно количеству кредиторов + количеству должников. За один перевод один из двух участников закрывает долг или недостатчу и выходит из расмотрения.
Меньше переводов получится, только если сумма остаточного долга равна кредиту и за один перевод выбывают 2 человека.
Минимизировать количество перводов тут - NP-полная задача. Она эквивалентна разбиению множества коредиторов и должников на подмножества с нулевой суммой.
Можно решить это за O(N 2^N) динамическим программированием по маске. Для 20 человек еще можно это дело посчитать довольно быстро, для 40 уже почти никак.
Хотя в среднем, жадный алгоритм наверно искоючит ситуацию, когда один человек получает много переводов от других.
Как я схлопнул 14 переводов в 5: бот для дележа расходов на голом Node без единой зависимости