| 1 | 1 | def find_fewest_coins(coins: list[int], target: int) -> list[int]: |
| 2 | | pass |
| 2 | # Edge Case: Target amount is negative |
| 3 | if target < 0: |
| 4 | raise ValueError("target can't be negative") |
| 5 | |
| 6 | # Edge Case: Target amount is zero |
| 7 | if target == 0: |
| 8 | return [] |
| 9 | |
| 10 | # Edge Case: No coins available |
| 11 | if not coins: |
| 12 | raise ValueError("can't make target with given coins") |
| 13 | |
| 14 | # Filter out non-positive coins |
| 15 | coins = [coin for coin in coins if coin > 0] |
| 16 | |
| 17 | # Edge Case: No valid coins after filtering |
| 18 | if not coins: |
| 19 | raise ValueError("can't make target with given coins") |
| 20 | |
| 21 | # Sort coins in descending order for optimization |
| 22 | coins.sort(reverse=True) |
| 23 | |
| 24 | # Initialize DP arrays |
| 25 | dp = [float('inf')] * (target + 1) |
| 26 | dp[0] = 0 |
| 27 | parent = [-1] * (target + 1) |
| 28 | |
| 29 | # Fill DP table |
| 30 | for i in range(1, target + 1): |
| 31 | for coin in coins: |
| 32 | if coin <= i and dp[i - coin] + 1 < dp[i]: |
| 33 | dp[i] = dp[i - coin] + 1 |
| 34 | parent[i] = coin |
| 35 | |
| 36 | # Edge Case: Impossible to make exact change with given coins |
| 37 | if dp[target] == float('inf'): |
| 38 | raise ValueError("can't make target with given coins") |
| 39 | |
| 40 | # Reconstruct the solution |
| 41 | result = [] |
| 42 | current = target |
| 43 | while current > 0: |
| 44 | coin = parent[current] |
| 45 | result.append(coin) |
| 46 | current -= coin |
| 47 | |
| 48 | # Return coins in ascending order |
| 49 | return sorted(result) |
| 50 | |
| 51 | # Handled Edge Cases: Target amount is negative, Target amount is zero, No coins available, No valid coins after filtering, Impossible to make exact change with given coins |