Разложить одно число на сумму других чисел

[eXeLe]

К сожалению, гугл подсказать не смогу, сплошь разложения на множители, квадраты и простые числа.
Смотрел в сторону задачи о ранце, но так и не смогу вписать ее в требуемые рамки.
Пытаюсь представить себе следующий алгоритм:
1. Есть некое положительное число X
2. Есть массив положительных чисел Y произвольной длинны
Нужно путем неограниченного сложения элементов массива Y получить число X, достаточно одного решения (все возможные не требуются).
По сути, нужно разложение числа на заданные повторяющиеся слагаемые (с неповторяющимися все было бы проще).

К примеру, число X = 109.
Массив Y = [15,14,9].

В результате применения алгоритма, должны получить информацию о том, что надо слежить:
15+15+15+14+14+9+9+9+9=109

У самого ничего в голову не лезет, кроме множественного перебора с вложенными циклами по размеру массива вида
for(int i1=0;(Y[0]*i1)<=X;i1++) {
...следующий цикл, где суммируем (Y[0]*i1) с (Y[1]*i2) в цикле или еще дальше вложенные циклы...
}

[Igors]

Ну если "тупенько", не претендуя ни на какую оптимальность и для небольшого набора чисел - то все просто (псевдокод)

Код

C++ (Qt)
bool FindSum( int sum, const std::vector <int> & vec, int from )
{
 if (from >= vec.size()) return false;
 int val = vec[from];
 int num = sum / val;
 if (!num) return false;
 int rem = sum % val;
 if (!rem) return true;
 for (int i = 0; i < num; ++i) 
  if (FindSum(rem + i * val, vec, from + 1))
   return true; 
 
 return FindSum(sum, vec, from + 1);
}
 

Запоминание результата добавите. На Вашем примере: считаем что 109 = 15 * 7 + x. Уходим на рекурс. Не вышло - тогда пробуем 109 = 15 * 6 + x. И.т.д.

[eXeLe]

Да, спасибо, работает нормально. Разве что клинит его, если сперва идут числа в массиве - больше указанной суммы - возвращает false на первой же проверке, на чем все и заканчивается.
Выложу код на Qt с выводом результата, вдруг кому-нибудь когда-нибудь пригодится =)

Код

C++ (Qt)
void Schet::on_knopka_clicked()
{
    int sum(ui->chisloX->text().toInt());
    QVector<int> Y;
    Y.push_back(15);
    Y.push_back(14);
    Y.push_back(9);
 
    bool Z(FindSum(sum, Y, 0));
    if(Z){
        ui->vivod->append(QString("Успех. Заданная сумма: %1").arg(sum));
        ui->vivod->append(QString(""));
    }
    else ui->vivod->append("Fail");
}
 
 
bool Schet::FindSum(int sum, const QVector<int> & vec, int from){
    if (from >= vec.size()) return false;
    int val = vec[from];
    int num = sum / val;
    if (!num) return false;
    int rem = sum % val;
    if (!rem){
        ui->vivod->append(QString("Число: %1 ; Множитель: %2").arg(vec[from]).arg(num));
        return true;
    }
    for (int i = 0; i < num; i++)
        if (FindSum(rem + i * val, vec, from+1)){
            ui->vivod->append(QString("Число: %1 ; Множитель: %2").arg(vec[from]).arg((sum-(rem + i * val))/vec[from]));
            return true;
        }
    return FindSum(sum, vec, from + 1);
}

[Igors]

Тут у нас помарочка, правильно так

Код

C++ (Qt)
// if (!num) return false;
if (!num) return FindSum(sum, vec, from + 1);