With coins {1, 3, 4} and a target of 6, give the minimum number of coins, the number of distinct combinations, and the answer the greedy algorithm produces. State the single loop change that converts a combination count into a permutation count.

With coins {1, 3, 4} and a target of 6, give the minimum number of coins, the number of distinct combinations, and the answer the greedy algorithm produces. State the single loop change that converts a combination count into a permutation count.

Approach: Run the two dynamic programs separately, one taking a minimum and one taking a sum, and check what the outer loop over coins is doing to the ordering of the choices.

2 coins minimum, 4 combinations, and greedy returns 3 coins. The minimum is 3 + 3, while greedy takes the largest coin first, giving 4 + 1 + 1 for 3 coins, so this coin system is not canonical and greedy failure is possible whenever a large coin blocks a better pairing. The combinations are 3+3, 4+1+1, 3+1+1+1 and 1 six times, so the count is 4. For the count, loop the coins on the outside and the amount on the inside, ways[a] += ways[a - c], which fixes an order on the coin types and counts each multiset once. Swapping the loop order so amount is outside and coins inside counts ordered sequences instead, giving permutations, which for this target is a much larger number since 4+1+1, 1+4+1 and 1+1+4 all count separately. Both dynamic programs are O(n * A) for n coin types and target A, and the minimising version uses min(dp[a - c] + 1), with dp at zero initialised to zero and every other entry to infinity.

Follow-up: What property of a coin system guarantees the greedy algorithm is optimal, and how would you test it for a given system?

Key concepts: coin change, greedy failure, combination count, loop order.