Subset_Sum.H File Reference

Subset sum algorithms: classical DP and meet-in-the-middle. More...

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_sort_utils.H>

Include dependency graph for Subset_Sum.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Subset_Sum_Result< T >
	Result of a subset sum computation. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::subset_sum_detail

Functions
template<std::integral T>
size_t	Aleph::subset_sum_detail::to_size_checked (const T value, const char *fn_name, const char *field_name)
template<std::integral T>
Array< size_t >	Aleph::subset_sum_detail::extract_values_checked (const Array< T > &values, const char *fn_name)
template<typename T >
Array< std::pair< long long, uint64_t > >	Aleph::subset_sum_detail::enumerate_sums (const Array< T > &arr, size_t start, size_t len)
template<std::integral T>
Subset_Sum_Result< T >	Aleph::subset_sum (const Array< T > &values, T target)
	Solve the subset sum problem via classical DP with reconstruction.
template<std::integral T>
bool	Aleph::subset_sum_exists (const Array< T > &values, T target)
	Check if a subset summing to target exists (space-optimized).
template<std::integral T>
size_t	Aleph::subset_sum_count (const Array< T > &values, T target)
	Count the number of subsets that sum to target.
template<std::integral T>
Subset_Sum_Result< T >	Aleph::subset_sum_mitm (const Array< T > &values, T target)
	Solve the subset sum problem via meet-in-the-middle (MITM).

Detailed Description

Subset sum algorithms: classical DP and meet-in-the-middle.

The subset sum problem is a decision problem in computer science that asks whether a subset of a given set of integers sums to a target value.

This header provides several variants:

• Classical DP: O(n * target) for integral values, includes reconstruction.
• Existence check: Optimized O(target) space version.
• Counting: Counts the number of distinct subsets that achieve the target.
• Meet-in-the-middle (MITM): Efficient for larger target values but smaller sets (up to ~40 elements).

Complexity

Variant	Time	Space
DP (reconstruction)	O(n * target)	O(n * target)
Existence Check	O(n * target)	O(target)
Meet-in-the-Middle	O(n * 2^(n/2))	O(2^(n/2))

Example

Array<int> values = {3, 34, 4, 12, 5, 2};
int target = 9;
 
// Solve Subset Sum
auto res = subset_sum(values, target);
// res.exists = true
// res.selected_indices = {2, 4} (indices of 4 and 5)

Definition in file Subset_Sum.H.