Generate a combination of minimum coins that sums to a given value | C ++ program for the above approach ; dp array to memoize the results ; List to store the result ; Function to find the minimum number of coins to make the sum equals to X ; Base case ; If previously computed subproblem occurred ; Initialize result ; Try every coin that has smaller value than n ; Check for INT_MAX to avoid overflow and see if result can be minimized ; Memoizing value of current state ; Function to find the possible combination of coins to make the sum equal to X ; Base Case ; Print Solutions ; Try every coin that has value smaller than n ; Add current denominations ; Backtrack ; Function to find the minimum combinations of coins for value X ; Initialize dp with - 1 ; Min coins ; If no solution exists ; Backtrack to find the solution ; Driver code ; Set of possible denominations ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100000 NEW_LINE int dp [ MAX + 1 ] ; list < int > denomination ; int countMinCoins ( int n , int C [ ] , int m ) { if ( n == 0 ) { dp [ 0 ] = 0 ; return 0 ; } if ( dp [ n ] != -1 ) return dp [ n ] ; int ret = INT_MAX ; for ( int i = 0 ; i < m ; i ++ ) { if ( C [ i ] <= n ) { int x = countMinCoins ( n - C [ i ] , C , m ) ; if ( x != INT_MAX ) ret = min ( ret , 1 + x ) ; } } dp [ n ] = ret ; return ret ; } void findSolution ( int n , int C [ ] , int m ) { if ( n == 0 ) { for ( auto it : denomination ) { cout << it << ' ▁ ' ; } return ; } for ( int i = 0 ; i < m ; i ++ ) { if ( n - C [ i ] >= 0 and dp [ n - C [ i ] ] + 1 == dp [ n ] ) { denomination . push_back ( C [ i ] ) ; findSolution ( n - C [ i ] , C , m ) ; break ; } } } void countMinCoinsUtil ( int X , int C [ ] , int N ) { memset ( dp , -1 , sizeof ( dp ) ) ; int isPossible = countMinCoins ( X , C , N ) ; if ( isPossible == INT_MAX ) { cout << " - 1" ; } else { findSolution ( X , C , N ) ; } } int main ( ) { int X = 21 ; int arr [ ] = { 2 , 3 , 4 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countMinCoinsUtil ( X , arr , N ) ; return 0 ; }