1function coinChange(coins, amount) {
2 const dp = Array(amount + 1).fill(Infinity);
3 dp[0] = 0;
4 const lastCoin = Array(amount + 1).fill(0);
5
6 for (const coin of coins) {
7 for (let a = coin; a <= amount; a++) {
8 const candidate = dp[a - coin] + 1;
9 if (candidate < dp[a]) {
10 dp[a] = candidate;
11 lastCoin[a] = coin;
12 }
13 }
14 }
15
16 // Reconstruct coin selection
17 const selected = [];
18 let rem = amount;
19 while (rem > 0) {
20 selected.push(lastCoin[rem]);
21 rem -= lastCoin[rem];
22 }
23 return { minCoins: dp[amount], selected };
24}