Meet in the Middle

/// Program C++ pentru a demonstra lucrul cu algoritmul Meet in the Middle pentru problema subset de suma maxima
/// https://www.geeksforgeeks.org/meet-in-the-middle/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll X[2000005],Y[2000005];

/// Gaseste toate sumele posibile de elemente din a[] si le memoreaza in x[]
void calcsubarray(ll a[], ll x[], int n, int c)
{
    for (int i=0; i<(1<<n); i++)
    {
        ll s = 0;
        for (int j=0; j<n; j++)
            if (i & (1<<j))
                s += a[j+c];
        x[i] = s;
    }
}

/// Returneaza suma maxima posibila mai mica sau egala cu S
ll solveSubsetSum(ll a[], int n, ll S)
{
    /// Se calculeaza toate sumele subsetului pentru prima si a doua jumatate
    calcsubarray(a, X, n/2, 0);
    calcsubarray(a, Y, n-n/2, n/2);
    int size_X = 1<<(n/2);
    int size_Y = 1<<(n-n/2);
    /// Se sorteaza Y (trebuie sa facem cautarea binara in el)
    sort(Y, Y+size_Y);
    /// Pentru a tine minte suma maxima a unui subset astfel incat suma maxima sa fie mai mica decat S
    ll max = 0;
    /// Traverseaza toate elementele lui X si face Cautare binara pentru o pereche in Y cu o suma maxima mai mica decat S.
    for (int i=0; i<size_X; i++)
    {
        if (X[i] <= S)
        {
            /// low_bound () intoarce prima adresa care are o valoare mai mare sau egala cu S-X [i]
            int p = lower_bound(Y, Y+size_Y, S-X[i]) - Y;
            /// Daca S-X[i] nu se afla in vectorul Y atunci micsoram p cu 1
            if (p == size_Y || Y[p] != (S-X[i]))
                p--;
            if ((Y[p]+X[i]) > max)
                max = Y[p]+X[i];
        }
    }
    return max;
}

/// Codul functiei principale
int main()
{
    ll a[] = {45, 34, 4, 12, 5, 2};
    int n=sizeof(a)/sizeof(a[0]);
    ll S = 42;
    printf("Cea mai mare valoare mai mica sau egala cu valoarea data "
           "sum este %lld\n", solveSubsetSum(a,n,S));
    return 0;
}