PHP: головоломка с заменой монеты

Question

Я работаю над Advent of Code как способ практиковать TDD и изучать PHPSpec. Я застрял на 17-м дне, который по сути является головоломкой для замены монет.

Эльфы снова купили слишком много эггонов - на этот раз 150 литров. Чтобы поместить все это в холодильник, вам нужно переместить его в меньшие контейнеры. Вы проводите инвентаризацию мощностей доступных контейнеров.

Например, предположим, что у вас есть контейнеры размером 20, 15, 10, 5 и 5 литров. Если вам нужно хранить 25 литров, есть четыре способа сделать это:

• 15 и 10
• 20 и 5 (первый 5)
• 20 и 5 (второй 5)
• 15, 5 и 5

Заполнение всех контейнеров полностью, сколько различных комбинаций контейнеров может точно соответствовать всем 150 литрам eggnog?

Вот мой код. Я написал тест, используя приведенные выше примеры. Метод combinations должен возвращать 4 для примера, но он возвращает 3. Он, похоже, не способен справиться с тем фактом, что существует более одного контейнера размером 5 литров.

Любые предложения, пожалуйста?

<?php 

namespace Day17; 

class Calculator 
{ 
    private $containers = []; 

    public function combinations($total, array $containers) 
    { 
     $combinations = $this->iterate($total, $containers); 
     return count($combinations); 
    } 

    /** 
    * http://stackoverflow.com/questions/12837431/find-combinations-sum-of-elements-in-array-whose-sum-equal-to-a-given-number 
    * 
    * @param $array 
    * @param array $combinations 
    * @param array $temp 
    * @return array 
    */ 
    private function iterate($sum, $array, $combinations = [], $temp = []) 
    { 
     if (count($temp) && !in_array($temp, $combinations)) { 
      $combinations[] = $temp; 
     } 

     $count = count($array); 
     for ($i = 0; $i < $count; $i++) { 

      $copy = $array; 
      $elem = array_splice($copy, $i, 1); 

      if (count($copy) > 0) { 

       $add = array_merge($temp, array($elem[0])); 
       sort($add); 
       $combinations = $this->iterate($sum, $copy, $combinations, $add); 

      } else { 

       $add = array_merge($temp, array($elem[0])); 
       sort($add); 
       if (array_sum($combinations) == $sum) { 
        $combinations[] = $add; 
       } 
      } 
     } 

     return array_filter($combinations, function ($combination) use ($sum) { 
      return array_sum($combination) == $sum; 
     }); 
    } 
} 

Answer 1

Использовать индексы массива доступных контейнеров в качестве значений комбинации.