화폐의 종류를 다르게 지정할 경우 없을 것이다.
#include <iostream>
#include<cstdio>
#include <string>
#define MAXN 50 // main()에서 사용
using namespace std;
int pay(int money, int bills[], int n, int num_bills, string s)
{
int count = 0;
int i, t;
if (n == 1)
{
if (money % bills[0] == 0)
{
string s2 = to_string(bills[0]) + " * " + to_string(money / bills[0]) + "\n";
s = s + s2;
std::cout << s <<std::endl;
return 1;
}
else
return 0;
}
t = money / bills[n - 1];
for (i = 0; i <= t; i++)
{
string s2 = to_string(bills[n - 1]) + " * " + to_string(i) + " + ";
string s3 = s + s2;
count += pay(money - bills[n - 1] * i, bills, n - 1, num_bills, s3);
}
return count;
}
int main()
{
int num_bills, money, i;
int bills[MAXN];
string s="";
printf("input number of bills : ");
scanf_s("%d", &num_bills);
printf("input bills : ");
for (i = 0; i < num_bills; i++)
scanf_s("%d", &bills[i]);
printf("input money : ");
scanf_s("%d", &money);
printf("answer : %d\n", pay(money, bills, num_bills, num_bills, s));
system("pause");
return 0;
}