Rust bestSum()

gistfile1.txt

use std::collections::HashMap;

fn bestSum(targetSum: i32, v: &Vec<i32>, memo: &mut HashMap<i32, Vec<i32>>) -> Vec<i32> {
    if targetSum == 0 { return vec![]; } 
    if targetSum < 0 { return vec![-1]; }
    if memo.contains_key(&targetSum) {
      return memo[&targetSum].clone();
    }
    
    let mut result: Vec<i32> = Vec::new();
    let mut len = 100000;

    for val in v {
        let rem = targetSum - val;
        let mut lastResult = bestSum(rem, v, memo);
        
        if lastResult.is_empty() || lastResult[0] != -1 {
            lastResult.push(*val);
            
            if lastResult.len() < len {
                result = lastResult;
                len = result.len();
            }
        }
    }
    
    memo.insert(targetSum, result);
    return memo[&targetSum].clone();
}


fn main() {
   let v = vec![1, 2, 5, 25];
   let targetSum = 99;
   let r = bestSum(targetSum, &v, &mut HashMap::new());
   println!("{:?}", r);
}