Question

How to find the total number of combinations of given coins to reach a specific amount in C++

Answer 1

#include <iostream>
#include <vector>

class Program {
public:
    void printVector(std::vector<int> const &v) {
        for (auto const &n: v) {
            std::cout << n << " ";
        }
    }
    
    int totalCombinations(int amount, std::vector<int>& coins) {
        std::vector<int> v(amount + 1);  
        v[0] = 1;
        
        for (auto& co:coins) {
            for (int i = co; i <= amount; i++) {
                v[i] += v[i - co];
            }
        }
        
        return v[amount];
    }
};

int main()
{
    std::vector<int> coins = {1, 2, 5, 10};
    int amount = 6;
    
    // [5,1], [2,2,2], [2,2,1,1], [2,1,1,1,1], [1,1,1,1,1,1]
    
    Program p;
    
    std::cout << p.totalCombinations(amount, coins);

}


 
/*
run:
 
5
 
*/

 

 

70+ SQL courses for beginners and professionals