<?php

error_reporting(-1);

$amount = 620;

$bills = array(
	10 => 5,
	50 => 0,
	200 => 10,
	500 => 10,
);

$keysBills = array_keys($bills);

$attempts = 0;

function countBillsSum($billsCopy) {
	
	$valuesBillsCopy = array_values($billsCopy);
	$keysBillsCopy = array_keys($billsCopy);
	
	for($i = 0; $i < count($billsCopy); $i++) {
		$result[$i] = $valuesBillsCopy[$i] * $keysBillsCopy[$i];
	}	
	$result = array_sum($result);
	return $result;	
}	

function findChange($amount, $keysBills, $bills, $billNumber) {
	
	$x = null;
	$debugOffset = str_repeat("  ", 3 - $billNumber);
	//echo "{$debugOffset}enter $billNumber\n";
	
	global $attempts;
	
	$currentBill = $keysBills[$billNumber];
	
	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);

	$amount = $amount - $currentBill*$currentMaxBills;
	
	for ($i = $currentMaxBills; $i >= 0; $i--) {
	
		$attempts++;
		$billsCopy = $bills;
		$billsCopy[$currentBill] = $i;
		
		$sum = countBillsSum($billsCopy);
		//echo "{$debugOffset}  i=$i, bills ".implode(", ", $billsCopy).", sum=$sum\n";
		
		if ($billNumber > 0) { 
			$x = findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
			if ($x) {
				return $x;
			}
		} elseif ($amount == 0) {
			//echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
			$x = implode(", ", array_values($billsCopy));
			return $x;
		} 
	}
}

echo findChange($amount, $keysBills, $bills, 3);
echo "\n".$attempts;