xkcd on python

Here's the basic recursive depth first search with caching. First in Python:

cache = {0: set([(0,)*len(options)])}
def orders(q):
  if q not in cache:
    cache[q] = set(v[:o]+(v[o]+1,)+v[o+1:] for o,j in enumerate(options) if q-j >= 0 for v in orders(q-j))
  return cache[q]

And then in (uglier) php:

$cache[0] = array(array_fill(0,sizeof($options),0));
function array_push_unique(&$haystack, $elem)
{
    $elemlen = sizeof($elem);
    $found = false;
    
    // need to check to see if elem is already in the array
    foreach($haystack as $val)
    {
        $vallen = sizeof($val);
        $foundsame = true;
        if ($vallen != $elemlen)
            continue;
        for ($i = 0; $i < $vallen; ++$i)
        {
            if ($val[$i] != $elem[$i])
            {
                $foundsame = false;
                break;
            }
        }
        if ($foundsame)
        {
            $found = true;
            break; 
        }
    }
    
    if (!$found)
    {
        array_push($haystack, $elem);
    }
}
// the main recursive function
function &calc_order($max_val)
{
    global $cache, $options;

    $opts = $options;

    reset($opts);

    if (!array_key_exists((int) $max_val, $cache))

    {

        $cache[$max_val] = array();

        foreach($opts as $key=>$item)

        {

            if (($max_val - $item['cost']) >= 0)

            {

                $res =& calc_order($max_val - $item['cost']);

                foreach($res as $ar)

                {

                    $ar[$key]++;

                    array_push_unique($cache[$max_val], $ar);

                }

            }

        }

    }

    return $cache[$max_val];

}