#include<iostream>
#include"partition.h"
#include<vector>
using namespace std;
vector<int> solve(vector<int> A)
{
    int ans1 = 1e9;
    int bits = 0;
    int total = 0;
    for(int i = 0; i < A.size(); i++) total+=A[i];
    for(int i = 0; i < (1<<A.size()); i++)
    {
        int temp = i;
        int curbit = 0;
        int cursum = 0;
        bool over = false;
        bool fail = false;
        int num = 0;
        while(temp)
        {
            int bit = temp & 1;
            if(bit)
            {
                num++;
                cursum+=A[curbit];
            }
            if((cursum > total/2 || (cursum == total/2 && total%2==0)) && !over) over = true;
            if((cursum > total/2 || (cursum == total/2 && total%2==0)) && over) fail = true;
            curbit++;
            temp = temp>>1;
        }
        if(!fail && abs((int)A.size() - num) < ans1)
        {
            bits = i;
            ans1 = abs((int)A.size() - num);
        }
    }
    int bits2 = bits;
    vector<int> ans;
    for(int i = 0; i < A.size(); i++)
    {
        int bit = bits & 1;
        if(bit) ans.push_back(i);
        bits = bits>>1;
    }
    for(int i = 0; i < A.size(); i++)
    {
        int bit = bits2 & 1;
        if(!bit) ans.push_back(i);
        bits2 = bits2>>1;
    }
    return ans;
}
