допустим у меня массив номиналов {10,5,2,1} и сумма 47
Сразу откладываем по 1 монете. Это сумма 18. Остаётся 47-18=29. Пытаемся набрать её произвольным образом. Получается (например, 2*10+1*5+2*2+0*1). Прибавляем те самые отложенные монеты, и получаем решение (одно из возможных): 3*10+2*5+3*2+1*1=47.
