# Coin Change
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/coin-change)
Canonical: https://scaleengineer.com/dsa/problems/coin-change
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [Atlassian](https://scaleengineer.com/companies/atlassian), [Capgemini](https://scaleengineer.com/companies/capgemini), [Deloitte](https://scaleengineer.com/companies/deloitte), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Mastercard](https://scaleengineer.com/companies/mastercard), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [BlackRock](https://scaleengineer.com/companies/blackrock), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Geico](https://scaleengineer.com/companies/geico), [Pinterest](https://scaleengineer.com/companies/pinterest), [Affirm](https://scaleengineer.com/companies/affirm), [Datadog](https://scaleengineer.com/companies/datadog), [Juniper Networks](https://scaleengineer.com/companies/juniper-networks)
---
## Problem
You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return _the fewest number of coins that you need to make up that amount_. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

**Input:** coins = [1,2,5], amount = 11
**Output:** 3
**Explanation:** 11 = 5 + 5 + 1

**Example 2:**

**Input:** coins = [2], amount = 3
**Output:** -1

**Example 3:**

**Input:** coins = [1], amount = 0
**Output:** 0

**Constraints:**

* `1 <= coins.length <= 12`
* `1 <= coins[i] <= 231 - 1`
* `0 <= amount <= 104`

# Approaches
## Brute-Force Recursion
This approach attempts to solve the problem by exploring every possible combination of coins that could sum up to the target amount. It uses a recursive function that for a given `amount`, tries using each coin and recursively calls itself for the `amount - coin`. The function then returns the minimum number of coins found among all branches of the recursion.
**Time:** O(S^N)

Where `S` is the number of coins and `N` is the amount. For each amount, the function branches out `S` times. This creates a recursion tree of depth up to `N`, leading to an exponential number of calls. · **Space:** O(amount)

The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the recursion can go as deep as the `amount` (e.g., if there is a coin of value 1).
**Pros:** Conceptually simple and follows a natural, divide-and-conquer logic.
**Cons:** Extremely inefficient due to redundant computations.; Will lead to a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial inputs.
### Explanation
The core of this method is a recursive helper function. This function calculates the minimum coins for a given amount by breaking it down into smaller subproblems. For an amount `A`, it tries subtracting each available coin `c` and recursively finds the minimum coins for the new amount `A - c`. The total coins for this path would be `1 + min_coins(A - c)`. The function explores all such paths and returns the minimum among them.

**Base Cases:**
- If the `amount` becomes 0, it means we've successfully made the change, so we need 0 more coins.
- If the `amount` becomes negative, it means the last coin used was too large, so this path is invalid.

The primary drawback is its performance. The same subproblem (e.g., finding the minimum coins for an amount of 5) is calculated multiple times through different recursive paths, leading to an exponential number of function calls.

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        
        int minCoins = Integer.MAX_VALUE;
        
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin);
            
            // If the subproblem has a solution (res >= 0) and it's better than what we have
            if (res >= 0 && res < minCoins) {
                minCoins = 1 + res;
            }
        }
        
        return (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
    }
}
```
### Algorithm
- Define a recursive function `solve(amount)`.
- **Base Case 1:** If `amount == 0`, return 0.
- **Base Case 2:** If `amount < 0`, return a value indicating impossibility (e.g., infinity or a special marker like -1).
- Initialize a variable `min_coins` to infinity.
- Iterate through each `coin` in the `coins` array:
  - Make a recursive call: `result = solve(amount - coin)`.
  - If the `result` indicates a valid solution was found for the subproblem, update `min_coins = min(min_coins, 1 + result)`.
- Return `min_coins`.
- In the main function, if the final result is infinity, it means no solution exists, so return -1. Otherwise, return the result.

## Top-Down Dynamic Programming (Memoization)
This approach enhances the brute-force recursion by using memoization, a dynamic programming technique. It stores the results of expensive function calls (subproblems) and returns the cached result when the same inputs occur again. This avoids re-computation and drastically improves performance.
**Time:** O(S * N)

Where `S` is the number of coins and `N` is the amount. Each subproblem `solve(i)` for `i` from 1 to `N` is computed exactly once. To compute each subproblem, we iterate through all `S` coins. · **Space:** O(N)

Where `N` is the amount. This space is used for the memoization array of size `N+1` and for the recursion stack, which can go up to depth `N`.
**Pros:** Significantly more efficient than brute-force.; Guarantees an optimal solution by exploring each subproblem only once.; The recursive structure can be more intuitive to write than the iterative bottom-up version.
**Cons:** May cause a `StackOverflowError` for very large `amount` due to deep recursion, though the problem constraints make this unlikely.; Has slightly more overhead than the bottom-up approach due to recursive function calls.
### Explanation
We introduce a memoization table (an array, `memo`) to store the minimum coins required for each amount from 0 to `amount`. Before computing the solution for an amount, we first check if the result is already in our `memo` table. If it is, we return it directly. If not, we compute it recursively as in the brute-force approach. Once the result is computed, we store it in the `memo` table before returning.

This way, each subproblem `solve(i)` for `i` from 0 to `amount` is computed only once. The results are then reused, pruning the recursion tree of all redundant branches.

```java
import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Use an array to store results for subproblems. 
        // -2 indicates not computed, -1 indicates impossible.
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -2);
        return solve(coins, amount, memo);
    }

    private int solve(int[] coins, int amount, int[] memo) {
        // Base cases
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        // Check memoization table
        if (memo[amount] != -2) {
            return memo[amount];
        }

        int minCoins = Integer.MAX_VALUE;

        for (int coin : coins) {
            int result = solve(coins, amount - coin, memo);
            // If a solution exists for the subproblem
            if (result != -1) {
                minCoins = Math.min(minCoins, result + 1);
            }
        }

        // Store result in memo table before returning
        memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
        return memo[amount];
    }
}
```
### Algorithm
- Create a memoization array, `memo`, of size `amount + 1` to store the results of subproblems. Initialize it with a sentinel value (e.g., -2) to indicate an uncomputed state.
- Define a recursive helper function `solve(amount, memo)`.
- **Base Case 1:** If `amount == 0`, return 0.
- **Base Case 2:** If `amount < 0`, return -1 (impossibility).
- **Memoization Check:** If `memo[amount]` is not the sentinel value, return the stored result.
- Initialize `min_coins = infinity`.
- For each `coin` in `coins`:
  - Recursively call `res = solve(amount - coin, memo)`.
  - If `res` is not -1, update `min_coins = min(min_coins, 1 + res)`.
- Store the computed result in the memoization table: `memo[amount] = (min_coins == infinity) ? -1 : min_coins`.
- Return `memo[amount]`.

## Bottom-Up Dynamic Programming (Tabulation)
This is the iterative or 'tabulation' version of the dynamic programming solution. It builds the solution from the ground up, starting from amount 0 and iteratively computing the minimum coins for each amount up to the target. This approach avoids recursion entirely, making it very efficient and free from stack depth limitations.
**Time:** O(S * N)

Where `S` is the number of coins and `N` is the amount. This is due to the two nested loops: one iterating from 1 to `N` and the inner one iterating through all `S` coins. · **Space:** O(N)

Where `N` is the amount. We need an array of size `N+1` to store the DP table.
**Pros:** Highly efficient and robust, generally considered the standard solution.; Avoids recursion overhead and potential stack overflow errors.; Iterative logic can be easier to analyze for performance.
**Cons:** Can be slightly less intuitive to formulate for those more accustomed to recursive thinking.
### Explanation
We use an array `dp` of size `amount + 1`, where `dp[i]` will store the minimum number of coins needed to make change for amount `i`. We initialize `dp[0]` to 0 (0 coins for amount 0) and all other `dp[i]` to a sentinel value representing infinity (a good choice is `amount + 1`, as it's an impossible number of coins).

We then iterate from `i = 1` to `amount`. For each `i`, we try to form the amount using each available coin. For every `coin`, if `coin <= i`, we can potentially form amount `i` by taking one `coin` and adding it to the optimal solution for amount `i - coin`. The number of coins for this combination would be `1 + dp[i - coin]`. We take the minimum over all possible coins.

The final answer is stored in `dp[amount]`. If its value is still the initial infinity value, it means the amount cannot be formed.

```java
import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] will store the minimum number of coins for amount i.
        int[] dp = new int[amount + 1];
        
        // A value of amount + 1 represents infinity, since we can't use more coins than the amount itself.
        int max = amount + 1;
        Arrays.fill(dp, max);
        
        // Base case: 0 coins are needed for amount 0.
        dp[0] = 0;
        
        // Build up the dp table from amount 1 to the target amount.
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    // dp[i - coin] would be the min coins for the remaining amount.
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // If dp[amount] is still 'max', it was never updated, meaning it's impossible.
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
```
### Algorithm
- Create a DP array, `dp`, of size `amount + 1`.
- Initialize `dp[0] = 0` and all other elements `dp[i]` to a value representing infinity (e.g., `amount + 1`).
- Loop for `i` from 1 to `amount` (representing the target amounts):
  - Inside, loop through each `coin` in the `coins` array:
    - If `coin <= i`, it's possible to use this coin.
    - Update the minimum coins for amount `i`: `dp[i] = min(dp[i], 1 + dp[i - coin])`.
- After the loops, if `dp[amount]` is still the infinity value, it means the amount is unreachable, so return -1.
- Otherwise, return `dp[amount]`.

# Solutions
### Java

```java
class Solution {
public
  int coinChange(int[] coins, int amount) {
    final int inf = 1 << 30;
    int n = amount;
    int[] f = new int[n + 1];
    Arrays.fill(f, inf);
    f[0] = 0;
    for (int x : coins) {
      for (int j = x; j <= n; ++j) {
        f[j] = Math.min(f[j], f[j - x] + 1);
      }
    }
    return f[n] >= inf ? -1 : f[n];
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange =
  function (coins, amount) {
    const n = amount;
    const f = Array(n + 1).fill(1 << 30);
    f[0] = 0;
    for (const x of coins) {
      for (let j = x; j <= n; ++j) {
        f[j] = Math.min(f[j], f[j - x] + 1);
      }
    }
    return f[n] > n ? -1 : f[n];
  };

```

### Python

```python
''' >>> float("inf") inf >>> float("inf") + 1 inf ''' class Solution ( object ): def coinChange ( self , coins , amount ): """ :type coins: List[int] :type amount: int :rtype: int """ dp = [ float ( "inf" )] * ( amount + 1 ) dp [ 0 ] = 0 for i in range ( 1 , amount + 1 ): for coin in coins : if i - coin >= 0 : dp [ i ] = min ( dp [ i ], dp [ i - coin ] + 1 ) return dp [ - 1 ] if dp [ - 1 ] != float ( "inf" ) else - 1 ############ class Solution : def coinChange ( self , coins : List [ int ], amount : int ) -> int : dp = [ amount + 1 ] * ( amount + 1 ) dp [ 0 ] = 0 for coin in coins : for j in range ( coin , amount + 1 ): dp [ j ] = min ( dp [ j ], dp [ j - coin ] + 1 ) return - 1 if dp [ - 1 ] > amount else dp [ - 1 ]
```

### CPP

```cpp
class Solution {
public:
  int coinChange(vector<int> &coins, int amount) {
    int n = amount;
    int f[n + 1];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int x : coins) {
      for (int j = x; j <= n; ++j) {
        f[j] = min(f[j], f[j - x] + 1);
      }
    }
    return f[n] > n ? -1 : f[n];
  }
};

```