Equal Partition

PROBLEM

Given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both subsets is equal.

#include <iostream>
#include <vector>
#include <format>
#include <algorithm>
#include <ranges>
#include <numeric>
#include <any>

class EqualPartitionSolver {
private:
    class DpEntry {
    public:
        bool isPossible = false;
        std::vector<int> indices = {};
    };
public:
    std::optional<std::vector<int>> solve(std::vector<int> const& values) {
        if (values.empty()) {
            return std::vector<int> {};
        }

        auto sum = std::reduce(values.cbegin(), values.cend());

        if (sum % 2 == 1) {
            return {};
        }

        int halfSum = sum / 2;

        std::vector<DpEntry> dp(halfSum + 1);
        dp[0].isPossible = true;

        std::ranges::for_each(
                values | std::views::enumerate,
                [&, maxSumYet = 0] (auto const& indexValueTuple) mutable {
                    auto [index, value] = indexValueTuple;

                    maxSumYet += value;
                    maxSumYet = std::min(maxSumYet, halfSum);

                    for (int c = maxSumYet; c >= value; --c) {
                        if (dp[c].isPossible) {
                            continue;
                        }

                        if (!dp[c - value].isPossible) {
                            continue;
                        }

                        dp[c].isPossible = true;
                        dp[c].indices = dp[c - value].indices;
                        dp[c].indices.push_back(index);
                    }
                }
        );

        if (!dp[halfSum].isPossible) {
            return {};
        }

        return dp[halfSum].indices;
    }
};

int main() {
    EqualPartitionSolver equalPartitionSolver;

    auto solution = equalPartitionSolver.solve({1, 1, 3, 4, 7});

    std::cout << std::format("isPossible: {}", solution.has_value()) << std::endl;

    solution.and_then([](auto const& indices) -> std::optional<std::any> {
        std::cout << "indices: ";
        std::ranges::for_each(indices, [](auto const& index) { std::cout << std::format("{} ", index); });
        std::cout  << std::endl;
        return {};
    });
}

/*
 * isPossible: true
 * indices: 0 2 3
 */