Как подобрать слагаемые суммы?

Question

[Денис Шпуганич]

Есть задача найти слагаемые для определённой суммы.
Слагаемые заданны массивом.
Могут использоваться несколько раз.

Например:
Из слагаемых [1,2,6,10] нужно получить сумму 15
Ответом будет 10+2+2+1

Есть реализация для не повторяющихся слагаемых но это не то, что нужно:

function findSummand($sum, $parts, $depth = 0) {
    static $args = array();
    
    foreach ($parts as $k => $part) 
    {
        if ($part == $sum) 
        {
            $args[$depth] = $part;
            return true;
        }
        if ($part < $sum) 
        {
            $args[$depth] = $part;
            if (findSummand($sum - $part, array_slice($parts, $k + 1), $depth + 1)) 
            {
                if ($depth == 0) 
                {
                    return $args;
                }
                return true;
            }
        }
    }
    
    if ($depth == 0) {
        return 'Решение не найдено';
    }
}

Answer 1

[Dimonchik]

так а что тут сложного?
мало того что задача не о рюкзаке,а конкретной цифре, так еще и повторять можно

начинаешь с разложения на слагаемые, а дальше итерация - перебор недостающей дельты и наличными элементами

Answer 2

[Boris Köln]

Есть реализация для не повторяющихся слагаемых

А для повторяющихся надо убрать array_slice.

P.S. Если бы вы сами писали указанный код, то модицифицировать его не составило бы труда. А если взять этот код у одногруппника, на Тостере получить ответ и сдать результат для зачета, то ума от этого не прибавится.

Answer 3

[Дмитрий]

Доброй ночи.
Попробуйте начать со следующей функции

function sumInit($array, $sum){
      static $new = [];
      static $result = null;
      if(array_sum($new) == $sum){
         $result = $new;
      }
      else{
        $max = max($array);
        $key_max = array_keys($array, max($array))[0];
        if((array_sum($new) + $max) <= $sum){
          $new[] = $max;  
        } 
        else if((array_sum($new) + $max) > $sum){
          unset($array[$key_max]);     
        }      
        sumInit($array, $sum); 
      }
      if($result != null){
        return $result;
      } 
}