<?php

error_reporting(-1);

$amount = 240;

$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) {
	
	$debugOffset = str_repeat("  ", 3 - $billNumber);
	echo "{$debugOffset}enter $billNumber\n";
	
	global $attempts;
	
	$currentBill = $keysBills[$billNumber];
	
	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);
	
	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) { 
			findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
		} elseif (countBillsSum($billsCopy) == $amount) {
			echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
			break;
		} 
	}
	echo "{$debugOffset}end\n";
	return;
}

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

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

echo "\n".$attempts;