#include <bits/stdc++.h>
#include "partition.h"
using namespace std;

const int INF = 1e9 + 10;

int totalSum = 0;
vector <int> a;
vector <int> bestAns;
int ansValue = INF;

vector <int> curr;

void rec (int ind, int sumA) {
    if (sumA >= 1.0 * totalSum / 2) {
        if (abs((int)curr.size() - ((int)a.size() - (int)curr.size())) < ansValue) {
            bestAns.clear();
            for (int i = 0; i < curr.size(); i ++) bestAns.push_back(curr[i]);
            ansValue = abs((int)curr.size() - ((int)a.size() - (int)curr.size()));
        }

        return;
    }
    if (ind == a.size()) {
        return;
    }

    curr.push_back(ind);
    rec(ind + 1, sumA + a[ind]);
    curr.pop_back();
    rec(ind + 1, sumA);
}

vector<int> solve(vector<int> A) {
    a = A;
    bestAns.clear();
    ansValue = INF;
    totalSum = 0;

    for (int i = 0; i < A.size(); i ++) totalSum += a[i];

    // cout << totalSum << endl;
    rec(0, 0);

    vector<int> finalAnswer;

    // cout << ansValue << endl;
    finalAnswer = bestAns;
    int ind = 0, i = 0;
    while (i < A.size()) {
        if (ind < bestAns.size() && bestAns[ind] == i) {
            ind ++;
            i ++;
        } else {
            finalAnswer.push_back(i);
            i ++;
        }
    }

    return finalAnswer;
}