零钱兑换-输出组合数

 1.暴力递归

（1）剩余金额小于0，无解

        剩余金额等于0，有解

        剩余金额大于0，继续递归

（2）从大的硬币到小的硬币，可以减少循环次数

#include <bits/stdc++.h>
using namespace std;int amount;
int coins[10]={5,2,1};
int res(int index,int* coins,int remainder)
{
//    剩余金额小于0，无解if(remainder<0){return 0;}
//    剩余金额等于0，有解else if(remainder==0){return 1;}
//    剩余金额大于0，继续递归else{int mycount=0;for(int i=index; i<3; i++){mycount+=res(i,coins,remainder-coins[i]);}return mycount;}}int main()
{amount=5;cout<<res(0,coins,amount);
}

如果要输出方案的话要用栈，让gpt写一下

#include <iostream>
#include <stack>
using namespace std;int amount;
int coins[10] = {1, 2, 5};void printCombination(stack<int>& combination) {stack<int> tempStack;while (!combination.empty()) {tempStack.push(combination.top());combination.pop();}cout << "Combination: ";while (!tempStack.empty()) {cout << tempStack.top() << " ";combination.push(tempStack.top());tempStack.pop();}cout << endl;
}int res(int index, int* coinList, int remainder, stack<int>& combination) {if (remainder < 0) {return 0;} else if (remainder == 0) {printCombination(combination);return 1;} else {int mycount = 0;for (int i = index; i < 3; i++) {combination.push(coins[i]);mycount += res(i, coinList, remainder - coins[i], combination);combination.pop();}return mycount;}
}int main() {amount = 5;stack<int> combination;cout << "Total combinations: " << res(0, coins, amount, combination) << endl;return 0;
}