Монеты: проблема сдачи с данными номиналами

coins_change.php

<?php
/**
* Первый подход (неверный), пытаемся погасить остаток максимальным номиналом
*
* O(m), m - колич. монет
*
* @return bool
*/
function canPayWithoutChangeBrute($sum, array $denominations)
{
    rsort($denominations);
    $denominations = array_filter($denominations);

    $modulo = array_reduce($denominations, function($remainder, $coin) {
        return $remainder % $coin;
    }, $sum);

    return $modulo === 0 ? true : false;
}

// canPayWithoutChangeBrute(100, [3, 7, 15]); // `true` (15*6 + 7*1 + 3*1)
// canPayWithoutChangeBrute(134, [25, 4, 10]); // `false`, but must be `true` (25*4 + 10*3 + 4*1)

/**
* Второй подход: для нахождения кол-ва вариантов оплаты 
* применим рекурсию с сохраненим состояния
*
* O(n*m), где n - сумма, m - колич. монет
*
* @return bool
*/
function canPayWithoutChange($sum, array $denominations)
{
    $denominations = array_filter($denominations);

    $waysToPay = payRecursion($sum, $denominations, $index = 0, $memory = []);

    return (bool) $waysToPay;
}

function payRecursion($sum, array $denominations, int $index, array $memory) {
    // дошли до конца суммы
    if ($sum === 0) {
        return 1;
    }

    // если номиналы кончились, вариантов не осталось
    if ($index >= count($denominations)) {
        return 0;
    }

    // результат был рассчитан ранее
    $key = $sum . '_' . $index;
    if (isset($memory[$key])) {
        return $memory[$key];
    }

    // сколько заплатили
    $payed = 0;
    // варианты оплаты (кол-во комбинаций монет)
    $ways = 0;

    while ($payed <= $sum) {
        // остаток для уплаты
        $remainder = $sum - $payed;

        // входим в рекурсию с уменьшенной суммой и следующей монетой
        $ways += payRecursion($remainder, $denominations, $index + 1, $memory);

        // увеличиваем уплаченную сумму
        $payed += $denominations[$index];
    }
    // оптимизация (кол-во решений для монеты)
    $memory[$key] = $ways;

    return $ways;
}

var_dump(canPayWithoutChange(100, [7, 19])); // false
var_dump(canPayWithoutChange(134, [25, 4, 10])); // true
var_dump(canPayWithoutChange(100, [4, 14])); // true
var_dump(canPayWithoutChange(5, [0])); // false