#pragma once

#include <vector>
#include <cstddef>
#include <cstdint>
#include <string>
#include <set>
#include <map>

struct Subsets {
    void BuildMasksForLeftPart(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask, int border);

    void BuildMasksForRightPart(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask, int border);

    int64_t SumOfMask(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask);

    std::vector<size_t> first_indices;
    std::vector<size_t> second_indices;
    bool exists = false;

    std::set<char> symbols = {'0', '1', '2'};
    std::map<int64_t, std::string> left_sums;
};

Subsets FindEqualSumSubsets(const std::vector<int64_t>& data);



#include "find_subsets.h"
#include <vector>

#include <iostream>

Subsets FindEqualSumSubsets(const std::vector<int64_t>& data) {
    Subsets subsets;
    int border = data.size() / 3;
    subsets.BuildMasksForLeftPart(data, 0, border, "", border);
    for (auto& [k, v] : subsets.left_sums) {
        std::cout << k << ' ' << v << std::endl;
    }
//    subsets.BuildMasksForRightPart(data, border + 1, data.size() - border, "", data.size());
    return subsets;
}

//void Subsets::BuildMasksForRightPart(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask, int border) {
//    if (exists) {
//        return;
//    }
//    if (mask.size() == border) {
//        if (left_sums.contains(SumOfMask(vector, from, to, mask))) {
//            exists = true;
//            return;
//        }
//        return;
//    }
//    for (char elem : symbols) {
//        mask.push_back(elem);
//        BuildMasksForLeftPart(vector, from, to, mask, border);
//        mask.pop_back();
//    }
//}

// TODO наверное стоит переделать через классы
void Subsets::BuildMasksForLeftPart(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask, int border) {
    if (mask.size() == border) {
        left_sums.insert({SumOfMask(vector, from, to, mask), mask});
        return;
    }
    for (char elem : symbols) {
        mask.push_back(elem);
        BuildMasksForLeftPart(vector, from, to, mask, border);
        mask.pop_back();
    }
}
int64_t Subsets::SumOfMask(const std::vector<int64_t>& vector, size_t from, size_t to, std::string mask) {
    int64_t result = 0;
    for (size_t i = from; i < to; ++i) {
        if (mask[i] == 1) {
            result += vector[i];
        } else if (mask[i] == 2) {
            result -= vector[i];
        }
    }
    return result;
}