1. vector<vector<int>> dp(102, vector<int>(102, -1)); // Using a vector for memoization
2.  
3. int minCoinsMemo(int coins[], int sum, int n, vector<int>& chosenCoins) {
4.     if (sum == 0) return 0;
5.     if (n == 0 || sum < 0) return INT_MAX; // Return a large value for invalid cases
6.  
7.     if (dp[n][sum] != -1) return dp[n][sum];
8.  
9.     if (coins[n - 1] <= sum) {
10.         dp[n][sum] = min(minCoinsMemo(coins, sum, n - 1, chosenCoins), 1 + minCoinsMemo(coins, sum - coins[n - 1], n, chosenCoins));
11.     } else {
12.         dp[n][sum] = minCoinsMemo(coins, sum, n - 1, chosenCoins);
13.     }
14.  
15.         return dp[n][sum];
16. }
17.  
18. void Print(int coins[],int n, int sum, vector<int> &chosenCoins;){
19.     int i = n;
20.         int j = sum;
21.         while (i > 0 && j > 0) {
22.             if (dp[i][j] == dp[i - 1][j]) {
23.                 i--;
24.             } else {
25.                 cout<<coins[i - 1]<<' ';
26.                 j -= coins[i - 1];
27.             }
28.         }
29. }
30.  
31. int main() {
32.     int sum = 7;
33.     int coins[] = {1, 2, 5};
34.     vector<int> chosenCoins;
35.     int n = sizeof(coins) / sizeof(coins[0]);
36.  
37.     int result = minCoinsMemo(coins, sum, n, chosenCoins);
38.  
39.     if (result == INT_MAX) {
40.         cout << "It's not possible to make the sum " << sum << " using the given coins." << endl;
41.     } else {
42.         cout << "Minimum number of coins required to make the sum " << sum << " is: " << result << endl;
43.     }
44.    
45.     Print(coins, n, sum, chosenCoins);
46.    
47.    
48.  
49.     return 0;
50. }