Дан набор гирек массой m1, . . . , mN . Можно ли их разложить на три кучки равной массы? Формат входных данных Первая строка входных данных содержит натуральное число N, не превышающее 60. Во второй строке через пробел записаны N натуральных чисел mi , не превышающих 60. Формат выходных данных Выведите три строки, описывающие наборы гирек, либо число -1, если решение не существует. В каждой строке сначала выведите количество гирек в соответствующем наборе, а затем через пробел номера гирек в наборе. Реши с помощью С++. Ограничения 1 секунда.

#include <iostream> #include <vector> #include <algorithm>

bool partition(std::vector<int>& weights, std::vector<int>& subset1, std::vector<int>& subset2, std::vector<int>& subset3, int index, int sum1, int sum2, int sum3) { if (index == weights.size()) { return sum1 == sum2 && sum2 == sum3; }

if (sum1 == sum2 && sum2 == sum3) {
    return true;
}

bool canPartition1 = false, canPartition2 = false, canPartition3 = false;

if (sum1 + weights[index] <= sum2 && sum1 + weights[index] <= sum3) {
    subset1.push_back(weights[index]);
    canPartition1 = partition(weights, subset1, subset2, subset3, index + 1, sum1 + weights[index], sum2, sum3);
    if (!canPartition1) {
        subset1.pop_back();
    }
}

if (!canPartition1 && sum2 + weights[index] <= sum1 && sum2 + weights[index] <= sum3) {
    subset2.push_back(weights[index]);
    canPartition2 = partition(weights, subset1, subset2, subset3, index + 1, sum1, sum2 + weights[index], sum3);
    if (!canPartition2) {
        subset2.pop_back();
    }
}

if ((!canPartition1 && !canPartition2) && sum3 + weights[index] <= sum1 && sum3 + weights[index] <= sum2) {
    subset3.push_back(weights[index]);
    canPartition3 = partition(weights, subset1, subset2, subset3, index + 1, sum1, sum2, sum3 + weights[index]);
    if (!canPartition3) {
        subset3.pop_back();
    }
}

return canPartition1 || canPartition2 || canPartition3;

}

int main() { int N; std::cin >> N;

std::vector<int> weights(N);
for (int i = 0; i < N; i++) {
    std::cin >> weights[i];
}

std::vector<int> subset1, subset2, subset3;

if (partition(weights, subset1, subset2, subset3, 0, 0, 0, 0)) {
    std::cout << subset1.size() << " ";
    for (int i = 0; i < subset1.size(); i++) {
        std::cout << subset1[i] << " ";
    }
    std::cout << std::endl;

    std::cout << subset2.size() << " ";
    for (int i = 0; i < subset2.size(); i++) {
        std::cout << subset2[i] << " ";
    }
    std::cout << std::endl;

    std::cout << subset3.size() << " ";
    for (int i = 0; i < subset3.size(); i++) {
        std::cout << subset3[i] << " ";
    }
    std::cout << std::endl;
} else {
    std::cout << "-1" << std::endl;
}

return 0;

}