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

task137.cpp

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

// Непосредственная реализация алгоритма
bool task137_impl(int n, std::vector<int>& v) {
	if (n == 1)
		return true;

	bool dividorFound = false;
	for (int i = 9; i >= 2; --i) {
		if (n % i == 0) {
			dividorFound = true;
			v.push_back(i);
      
      // Проверка делителя: если все ок, поиск окончен
			if (task137_impl(n / v.back(), v))
				break;
      
      // Иначе откат на предыдущий шаг и проба следующего делителя
			v.pop_back();
			dividorFound = false;
		}
	}
	return dividorFound;
}

// Обертка для красивого вызова и сокрытия внутренней кухни
std::vector<int> task137(int number) {
	std::vector<int> result{};

	if (!task137_impl(number, result))
		return { -1 };
	
	std::sort(result.begin(), result.end());
	return result;
}

// Метод для облегчения вывода вектора в консоль
template <typename T>
std::string toString(const std::vector<T>& v) {
	std::stringstream oss;
	for (const auto& i : v)
		oss << i;
	return oss.str();
}

int main(void) {
	auto ns = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 34, 72, 81, 100,
             168, 216, 324, 330, 432, 648, 1000, 2520, 4212, 7350, 11155, 21600, 30240, 1000000};

	for (const auto& n : ns)
		std::cout << n << ":\t" << toString(task137(n)) << '\n';

	return 0;
}

task137.txt

https://t.me/unilecs
Task 137. Найти минимальное натуральное число по заданному произведению составляющих его цифр. Вывести -1, если число найти не удается.

По сути задача сводится к факторизации числа - нахождению его множителей.
Но вводится дополнительное ограничение - множители не должны превышать 10, ибо они выражаются цифрами.
Здесь реализован самый простой вариант факторизации - перебор. Перебор делителей осуществляется с бОльших цифр к меньшим.
Полученные делители складываются в вектор и сортируются в возрастающем порядке для получения минимального числа.
Если на каком-то шаге алгоритм не находит делитель в интервале [2, 9], происходит возвращение к предыдущему шагу и проба другого делителя.