Meet-in-the-Middle Subset Sum
(algo/sequence/subset_sum.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/sequence/subset_sum.hpp"

Overview

Finds the maximum sum of a subset that does not exceed a given limit. The array is split in half, the subset sums of both halves are generated in sorted order, and a two-pointer scan finds the best compatible pair.

The sorted half-sum lists are also exposed for other meet-in-the-middle algorithms. Every subset sum of the original array can be written as left_sums[i] + right_sums[j].

Template Parameters

• T: Value and sum type. T{} must be the additive identity. Values must support operator+ and operator<, and addition by a fixed value must preserve ordering. Every subset sum must be representable by T.

Methods

Method	Description	Complexity
std::pair<std::vector<T>, std::vector<T>> enumerate_half_subset_sums(const std::vector<T>& values)	Returns the sorted subset sums of values[0, N / 2) and values[N / 2, N).	$O(2^{N/2})$ time and space
T maximum_subset_sum(const std::vector<T>& values, const T& limit)	Returns the maximum subset sum not exceeding limit. Requires T{} <= limit.	$O(2^{N/2})$ time and space

Behavior

Each half-sum vector is sorted in ascending order, includes the empty-subset sum T{}, and preserves equal sums produced by different subsets. The input is not modified.

maximum_subset_sum includes the empty subset as a candidate, so it returns T{} when no positive subset sum fits. limit must not be less than T{}.

Materializing all $2^N$ full-array subset sums would require $O(2^N)$ output. Keeping the halves separate uses only $O(2^{N/2})$ time and memory.

Example

#include "algo/sequence/subset_sum.hpp"
#include <iostream>
#include <vector>

int main() {
    const std::vector<long long> values = {2, 3, 5, 7, 11};
    const long long limit = 17;

    std::cout << m1une::algo::maximum_subset_sum(values, limit) << '\n';

    const auto [left_sums, right_sums] =
        m1une::algo::enumerate_half_subset_sums(values);
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/subset_sum.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_SUBSET_SUM_HPP
#define M1UNE_ALGO_SEQUENCE_SUBSET_SUM_HPP 1

#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

namespace internal {

template <typename T>
std::vector<T> enumerate_sorted_subset_sums(
    const std::vector<T>& values,
    int left,
    int right
) {
    std::vector<T> sums(1, T{});
    std::vector<T> merged;

    for (int i = left; i < right; ++i) {
        const std::size_t size = sums.size();
        merged.clear();
        merged.reserve(size * 2);

        std::size_t without = 0;
        std::size_t with = 0;
        while (without < size && with < size) {
            const T with_current = sums[with] + values[i];
            if (with_current < sums[without]) {
                merged.push_back(with_current);
                ++with;
            } else {
                merged.push_back(sums[without]);
                ++without;
            }
        }
        while (without < size) {
            merged.push_back(sums[without]);
            ++without;
        }
        while (with < size) {
            merged.push_back(sums[with] + values[i]);
            ++with;
        }
        sums.swap(merged);
    }

    return sums;
}

}  // namespace internal

// Returns the sorted subset sums of values[0, n / 2) and values[n / 2, n).
template <typename T>
std::pair<std::vector<T>, std::vector<T>> enumerate_half_subset_sums(
    const std::vector<T>& values
) {
    const int n = int(values.size());
    const int middle = n / 2;
    return {
        internal::enumerate_sorted_subset_sums(values, 0, middle),
        internal::enumerate_sorted_subset_sums(values, middle, n)
    };
}

// Returns the maximum subset sum not exceeding limit.
template <typename T>
T maximum_subset_sum(const std::vector<T>& values, const T& limit) {
    assert(!(limit < T{}));
    auto [left_sums, right_sums] = enumerate_half_subset_sums(values);

    T answer{};
    std::size_t right_count = right_sums.size();
    for (const T& left : left_sums) {
        while (
            right_count > 0 &&
            limit < left + right_sums[right_count - 1]
        ) {
            --right_count;
        }
        if (right_count == 0) break;

        const T candidate = left + right_sums[right_count - 1];
        if (answer < candidate) answer = candidate;
    }
    return answer;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_SUBSET_SUM_HPP

#line 1 "algo/sequence/subset_sum.hpp"



#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

namespace internal {

template <typename T>
std::vector<T> enumerate_sorted_subset_sums(
    const std::vector<T>& values,
    int left,
    int right
) {
    std::vector<T> sums(1, T{});
    std::vector<T> merged;

    for (int i = left; i < right; ++i) {
        const std::size_t size = sums.size();
        merged.clear();
        merged.reserve(size * 2);

        std::size_t without = 0;
        std::size_t with = 0;
        while (without < size && with < size) {
            const T with_current = sums[with] + values[i];
            if (with_current < sums[without]) {
                merged.push_back(with_current);
                ++with;
            } else {
                merged.push_back(sums[without]);
                ++without;
            }
        }
        while (without < size) {
            merged.push_back(sums[without]);
            ++without;
        }
        while (with < size) {
            merged.push_back(sums[with] + values[i]);
            ++with;
        }
        sums.swap(merged);
    }

    return sums;
}

}  // namespace internal

// Returns the sorted subset sums of values[0, n / 2) and values[n / 2, n).
template <typename T>
std::pair<std::vector<T>, std::vector<T>> enumerate_half_subset_sums(
    const std::vector<T>& values
) {
    const int n = int(values.size());
    const int middle = n / 2;
    return {
        internal::enumerate_sorted_subset_sums(values, 0, middle),
        internal::enumerate_sorted_subset_sums(values, middle, n)
    };
}

// Returns the maximum subset sum not exceeding limit.
template <typename T>
T maximum_subset_sum(const std::vector<T>& values, const T& limit) {
    assert(!(limit < T{}));
    auto [left_sums, right_sums] = enumerate_half_subset_sums(values);

    T answer{};
    std::size_t right_count = right_sums.size();
    for (const T& left : left_sums) {
        while (
            right_count > 0 &&
            limit < left + right_sums[right_count - 1]
        ) {
            --right_count;
        }
        if (right_count == 0) break;

        const T candidate = left + right_sums[right_count - 1];
        if (answer < candidate) answer = candidate;
    }
    return answer;
}

}  // namespace algo
}  // namespace m1une

Back to top page