<?php

error_reporting(-1);

$amount = 740;

$bills = array(
	10 => 10,
	50 => 10,
	100 => 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) {
	
	echo "start $billNumber";
	
	global $attempts;
	
	$currentBill = $keysBills[$billNumber];
	
	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);
	
	for ($i = $currentMaxBills; $i >= 0; $i--) {
		
		echo "$i\n";
		
		$attempts++;
		$billsCopy = $bills;
		$billsCopy[$currentBill] = $i;
		
		if ($billNumber > 0) { 
			findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
		} elseif (countBillsSum($billsCopy) == $amount) {
			echo implode(", ", array_values($billsCopy))."\n";
			break;
		} 
	}
	echo "end\n";
	return;
}

echo findChange($amount, $keysBills, $bills, 3);

//echo selectMinimumBillsArray(findChange($amount, $keysBills, $bills, 0, array()));

echo "\n".$attempts;