3v4l.org

run code in 300+ PHP versions simultaneously
<?php function optimalChange(int $amount, array $denominations): ?array { if (!$amount) { return []; // happy ending } foreach ($denominations as $d) { if ($d <= $amount) { $deeper = optimalChange($amount - $d, $denominations); if ($deeper !== null) { $result = array_merge([$d], $deeper); break; // run up the recursive branch } } } return $result ?? null; } $target = 23; $denominations = [10, 5, 2]; // must be rsort()ed at declaration foreach (range(0, 35) as $target) { printf( "%s: %s\n", $target, json_encode( optimalChange($target, $denominations) ?: 'Sorry' ) ); }
Output for 8.1.0 - 8.1.33, 8.2.0 - 8.2.29, 8.3.0 - 8.3.26, 8.4.1 - 8.4.13
0: "Sorry" 1: "Sorry" 2: [2] 3: "Sorry" 4: [2,2] 5: [5] 6: [2,2,2] 7: [5,2] 8: [2,2,2,2] 9: [5,2,2] 10: [10] 11: [5,2,2,2] 12: [10,2] 13: [5,2,2,2,2] 14: [10,2,2] 15: [10,5] 16: [10,2,2,2] 17: [10,5,2] 18: [10,2,2,2,2] 19: [10,5,2,2] 20: [10,10] 21: [10,5,2,2,2] 22: [10,10,2] 23: [10,5,2,2,2,2] 24: [10,10,2,2] 25: [10,10,5] 26: [10,10,2,2,2] 27: [10,10,5,2] 28: [10,10,2,2,2,2] 29: [10,10,5,2,2] 30: [10,10,10] 31: [10,10,5,2,2,2] 32: [10,10,10,2] 33: [10,10,5,2,2,2,2] 34: [10,10,10,2,2] 35: [10,10,10,5]
preferences:
69.45 ms | 408 KiB | 5 Q