September 10, 2025
Many Hard Leetcode Problems are Easy Constraint Problems
Use the right tool for the job.
In my first interview out of college I was asked the change counter problem:
Given a set of coin denominations, find the minimum number of coins required to make change for a given number. IE for USA coinage and 37 cents, the minimum number is four (quarter, dime, 2 pennies).
I implemented the simple greedy algorithm and immediately fell into the trap of the question: the greedy algorithm only works for "well-behaved" denominations. If the coin values were [10, 9, 1] , then making 37 cents would take 10 coins in the greedy algorithm but only 4 coins optimally ( 10+9+9+9 ). The "smart" answer is to use a dynamic programming algorithm, which I didn't know how to do. So I failed the interview.
But you only need dynamic programming if you're writing your own algorithm. It's really easy if you throw it into a constraint solver like MiniZinc and call it a day.
int: total; array[int] of int: values = [10, 9, 1]; array[index_set(values)] of var 0..: coins; constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total; solve minimize sum(coins);
You can try this online here. It'll give you a prompt to put in total and then give you successively-better solutions:
coins = [0, 0, 37]; ---------- coins = [0, 1, 28]; ---------- coins = [0, 2, 19]; ---------- coins = [0, 3, 10]; ---------- coins = [0, 4, 1]; ---------- coins = [1, 3, 0]; ----------
... continue reading