algorithmdynamic-programmingcoin-change# Simple algorithm to compute coins that form minimum number of coins (or any valid number of coins) from a limited number of coins

I need to find the coins needed to make up a specified amount, not the number of ways or the minimum number of coins, but if the coins end up a minimal number then that's ideal.

For example, we have coins (1, 5, 25, 50) and we want to make up the amount 200.

If we had an unlimited number of coins we would get (50, 50, 50, 50) as the minimum number of coins. But if we had limits on the coins, e.g. maximum of two 50s, five 25's then we wouldn't be able to get that result but another list of coins instead: 50, 50, 25, 25, 25, 25 (more coins but that doesn't matter).

If no combination of coins can be made then an empty collection would be returned.

I've seen explanations that are not clear so I'm looking for clarity: think if you were going to code this to be maintained by other developers then how would you write the code?

A coded example would be ideal (C-syntax language preferred) but pseudocode should also work if it's as clear or clearer, as it should be; if you want to do both be my guest.

I'm thinking the algorithm should not be more than O(n*k) complexity.

This may be the closest thing I've seen so far, but the accepted answer isn't clear to me (anyone who could explain it, particularly the *k* part gets bonus points): Dynamic Programming Coin Change Limited Coins

Extra point if you can come up with a test for it.

Thanks for your help!

Solution

Thanks to both @user3386109 and @RBarryYoung; I based my answer on the subset sum problem and a Dynamic Programming solution:

```
public List<Integer> makeChange(int[] coins, int amount) {
var coinsSumToAmount = new boolean[coins.length][amount + 1];
for (int row = 0; row < coins.length; row++) {
coinsSumToAmount[row][0] = true;
for (int col = 1; col <= amount; col++) {
if (row == 0) {
if (col == coins[row]) {
coinsSumToAmount[row][col] = true;
}
}
else {
if (col < coins[row]) {
coinsSumToAmount[row][col] = coinsSumToAmount[row - 1][col];
}
else { // col >= coin
coinsSumToAmount[row][col] = coinsSumToAmount[row - 1][col] || coinsSumToAmount[row - 1][col - coins[row]];
}
}
}
}
if (coinsSumToAmount[coins.length - 1][amount]) {
// Backtrack to find actual coins
List<Integer> change = new ArrayList<>();
for (int row = coins.length - 1, col = amount; row >= 0 && col != 0; row--) {
if (row == 0 && coinsSumToAmount[row][col]) {
change.add(coins[row]);
}
else if (coinsSumToAmount[row][col] != coinsSumToAmount[row - 1][col]) {
change.add(coins[row]);
col -= coins[row];
}
}
return change;
}
else { // No solution found
return List.of();
}
}
```

- Facebook warm up challenge that I can't seem to figure out - Battleship
- For given sequences, build graph which will contain path for each sequence
- Print 2-D Array in clockwise expanding spiral from center
- Cartesian product of multiple arrays in JavaScript
- How can I optimize the algorithm to find the longest common subsequence (LCS) between two strings?
- Fill pattern of an arbitrary size in Intel hex file
- Efficiently create random sample from expand.grid output without using expand.grid
- How do I select a combination of two variables from a dataframe when each variable value can only be selected once?
- Heuristic function for water jug problem in A* search
- match all subitems in a string as different matches with regexp
- Check if all elements in a list are identical
- Time limit exceeded on the code: Check If a String Contains All Binary Codes of Size K
- Dynamic Programming - Minimum number of coins in C
- Simple script to find "lowest" available domain name
- How to get Floyd's triangle in JAVA with descending numbers
- Rearrange groups without repeating subjects
- how to calculate binary search complexity
- Find the maximum depth of a set of intervals
- Can a binary search tree be constructed from only the inorder traversal?
- Time complexity of StringBuilder reverse method
- Recommendation algorithm (and implementation) for finding similar items and users
- Get every combination of bits for two binary numbers
- The simplest algorithm for poker hand evaluation
- How to replace all occurrences of a character in string?
- Reverse integer bitwise without using loop
- Equal sides of an array in JS
- Why does BIDE use the semi-maximum period for search space pruning?
- C++ ICP Algorithm Memory Leak
- Looking to identify a "classic" problem and identify availble algorithms to solve it
- Algorithm to find true value range in bool array