Разложить массив по суммам чисел

Есть массив наподобие x = {21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,27};, надо его упаковать по суммам. То что есть пока еще не годно, все еще брутфорсю=)

//частоты (для [0,0,2,2] - [2,0,2])
inline auto e(std::vector<int>& z, int sz)
{
    std::vector<int> c(sz, 0);
    for (int i = 0; i < z.size(); i++)
        c[z[i]]++;
    return c;
}
inline void f(std::vector<int>& x, std::vector<int>& c, std::vector<std::vector<int>>& res, int ln)
{
#define n 4
    int sz = x.size();
    int d = std::pow(sz, n);
    for (int i = 0; i < d; i++)
    {
        int sum = 0;
        int j = i;
        for (int i = 0; i < n; i++, j /= sz)
            sum += x[j % sz];
        if (sum == ln)
        {
            std::vector<int> _res(n); // добавил n
            int j = i;
            for (int i = 0; i < n; i++, j /= sz)
                _res[i] = j % sz;
            auto d = e(_res, sz);// count
            int err = 0;
            for (int i = 0; i < sz; i++)
                if (d[i] > c[i])
                    err++;
            if (!err) // пропустить те на которые нету
            {
                std::sort(_res.begin(), _res.end());
                res.push_back(_res);
            }
        }
    }
    std::sort(res.begin(), res.end());
    auto it = std::unique(res.begin(), res.end());
    res.erase(it, res.end());
}
size_t best = -1;
int g(std::vector<int>& x, std::vector<int>& c, std::vector<int> parent, int depth, int ln)
{
    std::vector<std::vector<int>> res;
    f(x, c, res, ln);
    std::random_shuffle(res.begin(), res.end()); // для разнообразия =)
#pragma omp parallel for
    for (int i = 0; i < res.size(); i++)
    {
        auto y = x, d = c; // для каждого решения от f создается новые
   // массивы с обновленной информацией
        for (auto& z : res[i])
            d[z]--;
        for (int j = 0; j < d.size();)
        {
            if (!d[j])
            {
                y.erase(y.begin() + j);
                d.erase(d.begin() + j);
            }
            else
                j++;
        }
        auto _parent = parent; // результаты передаются выше,
    // здесь parent - уже не нужно
        for (auto& z : res[i])
            _parent.push_back(x[z]);
        _parent.push_back(-1);
        g(y, d, _parent, depth + 1, ln);
    }
/// print -->
    int tail = 0, sum = 0, i = 0, l = 0;
    for (auto& z : c)
        tail += z;
    if (best > tail)
    {
        best = tail, std::cout << "\ndepth = " << depth << ", tail = " << tail << '\n';
        for (auto& z : parent)
        {
            if (z == -1)
                std::cout << " = " << sum << std::endl, sum = i = 0, l++;
            else
            {
                if (!i++)
                    std::cout << l << ": ";
                std::cout << z << '+', sum += z;
            }
        }
        std::cout << '\n';
        for (int i = 0; i < c.size(); i++)
            while (c[i]--)
                std::cout << x[i] << '+';
    }
    return tail;
}
void main(int argc, char **argv)
{
    std::vector<int> c(x.back() - x.front() + 1, 0);
    for (int i = 0; i < x.size(); i++)
        c[x[i] - x.front()]++;
    auto it = std::unique(x.begin(), x.end());
    x.erase(it, x.end());
    std::vector<int> res;
    g(x, c, res, 0, strtoul(argv[1], 0, 10));
}

Как работает:

• функция f находит все сочетания (ограничения длины не должно быть, здесь 4), их (кол-во типов)^4, выбираются те сочетания, которые дают нужную сумму;
• при помощи g выбираются следующие сочетания, и идет продвижение до того как не будет возможности собрать нужную сумму;
• число 95 может быть другим, если вариант получится лучше

Основные сложности с тем как передать информацию дальше - я использую вектор parent чтобы передавать, не очень удачно. Судя по 1-му восхождению на вершину - дебагал размер 95 - вариантов 66520453480448000000`000 (=16*11*11*5*5*5*5*5*5*5*5*5*4*4*4*4* 4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*1*..)

Решение с хвостом 8 (45 по 118 и 2 по 101):

21+21+23+26+27
21+21+24+26+26
21+22+25+25+25
21+23+24+25+25
21+22+25+25+25
21+24+24+24+25
21+24+24+24+25
21+24+24+24+25
21+24+24+24+25
21+22+25+25+25
21+22+25+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+22+24+25+25
22+23+23+25+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+23+24+25
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
23+23+24+24+24
25+25+25+26
25+25+25+26