#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 = n / 2 + 1; j >= 0; j--) {
            for(auto [x, y] : v[j]) {
                if(y == i) continue;
                if(v[j + A[i]].count(x + 1) == 0) 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; 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;
    vector<int> vis(size, 0);
    for(int i = 0; i < amount; i++) {
        vis[v[position][amount - i]] = 1;
        res.push_back(v[position][amount - i]);
        backtracing = res.back();
        position -= A[backtracing];
    }
    for(int i = 0; i < size; i++) {
        if(vis[i] == 0) res.push_back(i);
    }
    return res;
}
