#!/usr/bin/perl
# xkcd 287
my %appetizers;
$appetizers{"mixed fruit"}=215;
$appetizers{"french fries"}=275;
$appetizers{"side salad"}=335;
$appetizers{"hot wings"}=355;
$appetizers{"mozarella sticks"}=420;
$appetizers{"sampler plate"}=580;

my @order;
my %possibleorders;
sub genorder {
	my ($moneyleft)=@_;
	if ($moneyleft==0)
	{
		my $currorder="";
		foreach $x (sort @order)
		{
			if ($currorder ne "")
			{ $currorder.=", " }
			$currorder.=$x;
		}
		if (!$possibleorders{$currorder})
		{
			print $currorder."\n";
			$possibleorders{$currorder}=1;
		}
		return;	
	}

	foreach $appetizer (keys %appetizers)
	{
		$price=$appetizers{$appetizer};
		if ($price<=$moneyleft)
		{
			push @order,$appetizer;
			genorder($moneyleft-$price);
			pop @order;
		}
	}
	return;
}

$money=1505;
print "We're trying to order exactly $money cents worth of appetizers.\n";
print "Possible solutions are:\n";
genorder($money);

# So do you want 7 pieces of mixed fruit, or
# double hot wings, mixed fruit and a sampler plate?