minimizing-coins

Problem

Minimum Number of Coins

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimized.

For example, if the coins are {1, 5, 7} and the desired sum is 11, an optimal solution is 5 + 5 + 1, which requires 3 coins.

---

Input

The first input line has two integers n and x:

• n — the number of coins
• x — the desired sum of money

The second line has n distinct integers c₁, c₂, ..., cₙ: the value of each coin.

---

Output

Print one integer: the minimum number of coins needed to produce the sum x.
If it is not possible, print -1.

---

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ x ≤ 10⁶
• 1 ≤ cᵢ ≤ 10⁶

Core logic

fn find_min(cache: &mut HashMap<u64, u64>, target_sum: u64, coins: &Vec<u64>) -> Option<u64> {
    if let Some(&entry) = cache.get(&target_sum) {
        return Some(entry);
    }

    let mut running_min: u64 = u64::MAX;

    for &coin in coins {
        if coin > target_sum {
            continue;
        }

        let new_target = target_sum - coin;
        
        if new_target == 0 {
            cache.insert(target_sum, 1); // cache base case
            return Some(1);
        }

        if let Some(path) = find_min(cache, new_target, coins) {
            let num_coins = 1 + path;
            if num_coins < running_min {
                running_min = num_coins;
            }
        }
    }

    if running_min != u64::MAX {
        cache.insert(target_sum, running_min);
        return Some(running_min);
    } else {
        cache.insert(target_sum, u64::MAX); // Mark as unreachable
        return None;
    }
}

Essentially, the purpose of the above code is to traverse a tree of possible coin decisions. As long as the coin denomination is smaller than the target, it's possible to recursively iterate through all combinations of coins while both caching and checking for a base case. This behavior is called memorization. The base case for any branch of the tree is when the target sum is equivalent to the coin of interest.