Тема: Комбінації чисел для заданої суми
Умови завдання такі.
Є певна сума грошей і монети різного номіналу.
Треба знайти всі можливі способи розміняти цю суму монетами.
Кількість монет необмежена.
Наприклад, сума 4, монети {1, 2}.
Комбінації монет {1,1,1,1} , {1, 1, 2}, {2, 2}.
Я пробував зробити щось таке:
unsigned long long countChange(const unsigned int money,
const std::vector<unsigned int>& coins)
{
int arr_size = coins.size();
std::vector<unsigned int> new_coins = coins;
unsigned long long answer { 0 };
int money_amount = money;
std::sort(new_coins.begin(), new_coins.end());
do {
for (int i = money_amount; i >= 0; --i) {
for (int j = 0; j < arr_size; ++j) {
cout << new_coins.at(j) * i << " ";
}
cout << endl;
}
} while (std::next_permutation(new_coins.begin(), new_coins.end()));
return answer;
}Застряг на комбінаціях, розумію, що треба брати монети
в різних кількостях і перебирати все це, але не знаю як у коді реалізувати без рекурсії.
