#include "partition.h"
#include <bits/stdc++.h>

std::vector<int> solve(std::vector<int> A) {

    const int N = A.size();
    int S = 0;

    std::vector<int> answer(N);
    for (int i = 0; i < N; i++) {
        answer[i] = i + 1;
        S += A[i];
    }

    std::vector<int> bestAnswer;
    int bestResult = INT_MAX;

    do {

        int result = 0;
        long long total = 0;

        for (const int &idx : answer) {
            total += A[idx];
            result++;

            if (total >= S / 2) {
                break;
            }
        }

        if (result < bestResult) {
            bestResult = result;
            bestAnswer = answer;
        }

    } while (std::next_permutation(answer.begin(), answer.end()));

    return bestAnswer;
}
