use std::collections::{HashMap as Map, HashSet as Set};

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct Combo {
    items: Vec<String>,
}

impl Combo {
    pub fn from_item(item: &str) -> Self {
        Self {
            items: vec![item.into()],
        }
    }
    pub fn add_item(&self, item: &str) -> Self {
        let mut modified = self.clone();
        modified.items.push(item.into());
        modified.items.sort();
        modified
    }
}

fn find_combos_inner(sorted_menu: &[(&str, f64)], target_price: f64, first_index: usize) -> Set<Combo> {
    let mut combos: Set<Combo> = Set::new();
    for (index, (item, price)) in sorted_menu[first_index..].iter().enumerate() {
        if *price > target_price {
            continue;
        } else if *price == target_price {
            let combo = Combo::from_item(item);
            combos.insert(combo);
        } else {
            let sub_combos = find_combos_inner(&sorted_menu, target_price - *price, index);
            for sub_combo in sub_combos {
                let combo = sub_combo.add_item(item);
                combos.insert(combo);
            }
        }
    }
    combos
}

fn find_combos(menu: &Map<&str, f64>, target_price: f64) -> Set<Combo> {
    let mut sorted_menu: Vec<(&str, f64)> = menu.clone().into_iter().collect();
    sorted_menu.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
    find_combos_inner(&sorted_menu, target_price, 0)
}

fn main() {
    let mut menu = Map::new();
    menu.insert("fries", 2.50);
    menu.insert("burger", 5.00);
    menu.insert("soda", 1.00);
    menu.insert("ice cream", 3.00);
    menu.insert("pickle", 0.50);
    menu.insert("chips", 1.20);
    menu.insert("candy bar", 1.10);
    menu.insert("onion rings", 3.00);
    menu.insert("curly fries", 2.75);
    menu.insert("candy corn", 1.60);
    // menu.insert("peanuts", 0.30);
    menu.insert("hot dog", 1.50);
    menu.insert("chili dog", 2.50);
    let target_price = 7.50;
    println!("Menu: {:#?}", &menu);
    println!("Target price: {}", target_price);
    println!("Solving...");
    let combos = find_combos(&menu, target_price);
    println!("# of possible combos: {}", combos.len());
    println!("All possible combos: {:#?}", &combos);
}