Simple algorithm to compute coins that form minimum number of coins (or any valid number of coins) from a limited number of coins

Question

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!

Answer 1

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();
    }
}