Swift solution to solve the "Minimum Coins to Make Amount [Greedy Algorithm]

Greedy Algorithm

A greedy algorithm is an approach for solving a problem by selecting the best option available at the moment. It doesn't worry whether the current best result will bring the overall optimal result.

The algorithm never reverses the earlier decision even if the choice is wrong. It works in a top-down approach.

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $18

Available coins are
$5 coin
$2 coin
$1 coin
There is no limit to the number of each coin you can use.

Here's a Swift solution to solve the "Minimum Coins to Make Amount" problem using a greedy approach (which works optimally for standard denominations like 5, 2, 1):

✅ Problem:
Given:

amount = 18
Unlimited supply of coins: [5, 2, 1]
Goal:

Find the minimum number of coins required to make the amount.
Return the list of coins used (optional).

✅ Swift Solution

func minimumCoins(for amount: Int, with coins: [Int]) -> (count: Int, usedCoins: [Int]) {
    var remaining = amount
    var result = [Int]()
    var totalCoins = 0

    // Sort coins in descending order for greedy approach
    let sortedCoins = coins.sorted(by: >)

    for coin in sortedCoins {
        while remaining >= coin {
            remaining -= coin
            result.append(coin)
            totalCoins += 1
        }
    }

    return (totalCoins, result)
}

// Example usage:
let coins = [5, 2, 1]
let amount = 18
let result = minimumCoins(for: amount, with: coins)

print("Minimum number of coins: \(result.count)")
print("Coins used: \(result.usedCoins)")

🧪 Output:

Minimum number of coins: 5
Coins used: [5, 5, 5, 2, 1]

✅ To Solve This Correctly: Use Dynamic Programming

Here’s the correct Swift solution using bottom-up DP that works for all coin sets:

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    if amount == 0 { return 0 }

    var dp = [Int](repeating: amount + 1, count: amount + 1)
    dp[0] = 0

    for i in 1...amount {
        for coin in coins {
            if i >= coin {
                dp[i] = min(dp[i], dp[i - coin] + 1)
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount]
}

**🧪 Test Cases:**

print(coinChange([2], 3))         // Output: -1 ✅
print(coinChange([1,2,5], 18))    // Output: 5  ✅ (5+5+5+2+1)
print(coinChange([2,5], 11))      // Output: 3  ✅ (5+5+1 not possible, so 5+2+2+2)

print(coinChange([5, 2, 1], 18))   // Output: 5
print(coinChange([2], 3))         // Output: -1 ✅ Correct!
print(coinChange([1, 3, 4], 6))   // Output: 2 (3+3 or 2+4)

🔍 Explanation:

We use a dp[i] array where dp[i] represents the minimum coins needed to make amount i
Initialize with amount + 1 (impossible value)
At the end, if dp[amount] > amount, that means it's not possible to make the amount

⏱ Time & Space Complexity:

Time: O(n × m), where n = amount, m = number of coins
Space: O(n)