Greedy Santa

/**
    Training OIS
    Greedy Santa ( christmas )
    https://training.olinfo.it/#/task/ois_christmas

    Author: Samuel Finocchio
    Date: 23/12/2019
    Solution 1: [ 19:36, 19:50 ] ( 50/100 ) Timeout
    Solution 2: [ 21:17, 21:22 ] ( 100/100 ) Added memoization
**/

#include <iostream>
#include <vector>
#include <limits>
#include <unordered_map>

using namespace std;

int solve ( vector < int > gifts, int index, int expense, int budget, unordered_map<string, int> &MEMO );

int main ( void )
{
    int giftsAmount, budget;
    cin >> giftsAmount >> budget;

    vector <int> gifts ( giftsAmount );

    int maximumExpense = 0;
    for ( int i = 0; i < giftsAmount; i++ ) {
        cin >> gifts [ i ];
        maximumExpense = maximumExpense + gifts [ i ];
    }

    if ( maximumExpense <= budget )
        cout << maximumExpense;
    else {
        unordered_map <string, int> MEMO;
        cout << solve ( gifts, 0, 0, budget, MEMO );
    }

    return 0;
}

int solve ( vector < int > gifts, int index, int expense, int budget, unordered_map <string, int> &MEMO ) {
    string memoIndex = to_string ( index ) + " - " + to_string ( expense );

    if ( MEMO.find ( memoIndex ) != MEMO.end() )
        return MEMO [ memoIndex ];

    if ( expense >= budget ) {
        MEMO [ memoIndex ] = expense;
        return expense;
    }

    if ( index == gifts.size() ) {
        MEMO [ memoIndex ] = numeric_limits<int>::max();
        return numeric_limits<int>::max();
    }

    int result = min (
        solve ( gifts, index + 1, expense + gifts [ index ], budget, MEMO ),
        solve ( gifts, index + 1, expense, budget, MEMO )
    );

    MEMO [ memoIndex ] = result;
    return result;
}