algorithm/coinchangeproblemsprint.cpp at master · phanthaiduong22/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>

using namespace std;

int coinChangeproblem(int total, int coins[],int n)
{
    vector<int>result(total+1);
    result[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=coins[i];j<=total;j++)
        {
            result[j]+=result[j-coins[i]];
        }
    }
    return result[total];
}
void printSolution(vector<int> &result, int total, int coins[],int n, int pos)
{
    if(total==0)
    {
        for(int r: result)
        {
            cout<<r<<" ";
        }
        cout<<endl;
    }
    for(int i=pos;i<n;i++)
    {
        if(total>=coins[i])
        {
            result.push_back(coins[i]);
            printSolution(result,total-coins[i],coins,n,i);
            result.pop_back();
        }
    }
}
int main()
{
    int total=10;
    int coins[]={1,2,5,10};
    int n=4;
    cout<<"Number Of Solutions : ";
    cout<<coinChangeproblem(total,coins,n)<<endl;
    vector<int>result;
    printSolution(result,total,coins,n,0);
    return 0;
}