| 1 | 1 | def find_fewest_coins(coins, target): |
| 2 | | pass |
| 2 | # Edge Case: Target amount is 0 |
| 3 | if target == 0: |
| 4 | return [] |
| 5 | |
| 6 | # Edge Case: Negative target amount |
| 7 | if target < 0: |
| 8 | raise ValueError("target can't be negative") |
| 9 | |
| 10 | # Edge Case: No coins available |
| 11 | if not coins: |
| 12 | raise ValueError("can't make target with given coins") |
| 13 | |
| 14 | # Remove zero-value coins and sort in descending order for optimization |
| 15 | coins = [coin for coin in coins if coin > 0] |
| 16 | if not coins: |
| 17 | raise ValueError("can't make target with given coins") |
| 18 | |
| 19 | # Sort coins in descending order to try larger denominations first |
| 20 | coins.sort(reverse=True) |
| 21 | |
| 22 | # Initialize DP arrays |
| 23 | # dp[i] will store the minimum number of coins needed to make amount i |
| 24 | dp = [float('inf')] * (target + 1) |
| 25 | # parent[i] will store which coin was used to reach amount i optimally |
| 26 | parent = [-1] * (target + 1) |
| 27 | |
| 28 | # Base case |
| 29 | dp[0] = 0 |
| 30 | |
| 31 | # Fill DP table |
| 32 | for i in range(1, target + 1): |
| 33 | for coin in coins: |
| 34 | if coin <= i and dp[i - coin] + 1 < dp[i]: |
| 35 | dp[i] = dp[i - coin] + 1 |
| 36 | parent[i] = coin |
| 37 | |
| 38 | # Edge Case: Impossible to make exact change |
| 39 | if dp[target] == float('inf'): |
| 40 | raise ValueError("can't make target with given coins") |
| 41 | |
| 42 | # Reconstruct the solution |
| 43 | result = [] |
| 44 | current = target |
| 45 | while current > 0: |
| 46 | coin_used = parent[current] |
| 47 | result.append(coin_used) |
| 48 | current -= coin_used |
| 49 | |
| 50 | # Return coins in ascending order as per examples |
| 51 | return sorted(result) |
| 52 | |
| 53 | # Handled Edge Cases: Target amount is 0, Negative target amount, No coins available, Impossible to make exact change |