So I recently had a look through my old blog posts and one in particular caught special interest.

It's been a long time since I solved these kinds of problems and I wanted to freshen up, at least a teeny tiny bit, so I rewrote the solution in Rust.

use std::collections::BTreeSet as Set;
use std::collections::HashMap as Map;

fn solve_subset_sum(input: &[i32], target: i32) -> Option<Set<i32>> {
    let mut possible_sums = Map::<i32, Set<i32>>::new();
    for elem in input.iter() {
        let mut new_sums = possible_sums.clone();
        for (prev_sum, mut components) in possible_sums.drain() {
            let new_sum = prev_sum + elem;
            components.insert(*elem);
            new_sums.insert(new_sum, components);
        }

        possible_sums.extend(new_sums);
        possible_sums.insert(*elem, { let mut s = Set::new(); s.insert(*elem); s });

        if possible_sums.contains_key(&target) {
            return possible_sums.remove(&target);
        }
    }
    return None;
}


fn main() {
    let input = vec![-6, -9, -10, -11, -15, 1, 2, 3, 4, -3];
    println!("Solution: {:?}", solve_subset_sum(&input, 0));
}

I realized I can use essentially a list of maps instead of a matrix of booleans. It makes the calculation of the solution trivial and is probably just a side-grade when it comes to compute and memory requirements, depending the input.