#include #include using namespace std; void helper(int num, int idx, vector& coins, vector& ans, vector& ds) { if (num == 0) { if (ans.empty() || (ans.size() > ds.size())) ans = ds; return; } if (idx == 0) { if (num % coins[idx] == 0) { int newCoins = num / coins[idx]; int copy = newCoins; while (copy--) { ds.push_back(coins[idx]); } if (ans.empty() || (ans.size() > ds.size())) ans = ds; copy = newCoins; while (copy--) { ds.pop_back(); } return; } return; } //take if (coins[idx] <= num) { ds.push_back(coins[idx]); helper(num - coins[idx], idx, coins, ans, ds); ds.pop_back(); } //no take helper(num, idx - 1, coins, ans, ds); } void getOptimalChanges(int num) { vector coins{ 2,5,10}; int n = (int)coins.size(); vector ans; vector ds; helper(num,n-1,coins,ans,ds); for (auto& elem : ans) cout << elem << " "; cout << endl; } int main() { int nums = 1; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 5; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 10; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 6; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 7; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 50; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); nums = 49; cout << "Changes for " << nums << " :" ; getOptimalChanges(nums); return 0; }