Change Rust

want-change.rs

use std::collections::HashMap;

// O(n^2)
// O(n)
fn want_change(have: Vec<i32>, want: i32) -> Vec<i32> {
  let mut map = HashMap::new(); // { num: i } 
  
  let mut res = vec![];
  
  // a + b === want 
  // want - a = b
  // want - b = a
  // 20 - 10 = 10
  // a + b + c = want
  // 37 - 25 - 1 - 1 = 10
  // 20 - 17 (current) = 10 (?? Seen - hashmap ??)
  for (i, num) in have.iter().enumerate() {
    let sum = res.iter().sum::<i32>();
    
    if sum + num <= want {
      res.push(*num);
    }
    
    let difference = want - num - sum; // 37 - 10 - 2 === 25
    
    match map.get(&difference) {
      Some(_idx) => {
        res.push(difference);
        break;
      } 
      None => {
        map.insert(num, i as i32);
      }
    }
  }
   
  res
}

fn main() {
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 20);
  println!("{:?}", res);
  
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 30);
  println!("{:?}", res);
  
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 35);
  println!("{:?}", res);
  
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 37);
  println!("{:?}", res);
  
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 50);
  println!("{:?}", res);
  
  let have = vec![25, 10, 1, 25, 10, 10, 1, 1, 1, 1, 5, 5];
	let res = want_change(have, 100);
  println!("{:?}", res);
}