vector<vector<int>> dp(102, vector<int>(102, -1)); // Using a vector for memoization

int minCoinsMemo(int coins[], int sum, int n, vector<int>& chosenCoins) {
    if (sum == 0) return 0;
    if (n == 0 || sum < 0) return INT_MAX; // Return a large value for invalid cases

    if (dp[n][sum] != -1) return dp[n][sum];

    if (coins[n - 1] <= sum) {
        dp[n][sum] = min(minCoinsMemo(coins, sum, n - 1, chosenCoins), 1 + minCoinsMemo(coins, sum - coins[n - 1], n, chosenCoins));
    } else {
        dp[n][sum] = minCoinsMemo(coins, sum, n - 1, chosenCoins);
    }

        return dp[n][sum];
}

void Print(int coins[],int n, int sum, vector<int> &chosenCoins;){
    int i = n;
        int j = sum;
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            } else {
                cout<<coins[i - 1]<<' ';
                j -= coins[i - 1];
            }
        }
}

int main() {
    int sum = 7;
    int coins[] = {1, 2, 5};
    vector<int> chosenCoins;
    int n = sizeof(coins) / sizeof(coins[0]);

    int result = minCoinsMemo(coins, sum, n, chosenCoins);

    if (result == INT_MAX) {
        cout << "It's not possible to make the sum " << sum << " using the given coins." << endl;
    } else {
        cout << "Minimum number of coins required to make the sum " << sum << " is: " << result << endl;
    }
    
    Print(coins, n, sum, chosenCoins);
    
    

    return 0;
}