#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> A) {
    int n = 0;
    int size = A.size();
    int maximum = 0;
    for(auto x : A) {
        n += x;
        maximum = max(x, maximum);
    }
    vector<map<int, int>> v(n);
    v[0][0] = -1;
    for(int i = 0; i < size; i++) {
        for(int j = 0; j < n / 2; j++) {
            for(auto [x, y] : v[j]) {
                if(y == i) continue;
                v[j + A[i]][x + 1] = i;
            }
        }
    }
    int best = 9999999;
    int position = 0;
    int backtracing = 0;
    int amount = 0;
    for(int i = (n + 1) / 2; i < (n + 1) / 2 + maximum; i++) {
        for(auto [x, y] : v[i]) {
            if(abs(size / 2 - x) < best || abs((size + 1) / 2 - x) < best) {
                best = min(abs(size / 2 - x), abs((size + 1) / 2 - x));
                position = i;
                backtracing = y;
                amount = x;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        cout << i << ": ";
        for(auto [x, y] : v[i]) {
            cout << x << "_" << y << " ";
        }
        cout << "\n";
    }
    vector<int> res;
    for(int i = 0; i < amount; i++) {
        cout << position << "_" << amount - i << "..\n";
        res.push_back(v[position][amount - i]);
        position -= A[backtracing];
        backtracing = res.back();
    }
    return res;
}
