Problem Statement
An array coins containing distinct positive coin denominations and a non-negative integer amount are given. Every denomination may be selected any number of times.
Return the minimum number of coins having a total value equal to amount. Return -1 after no exact combination can form the target. A target amount of 0 requires no coins and returns 0.
Example 1
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: Coins [5, 5, 1] form 11 with three coins, and no two available coins can form 11.
Example 2
Input: coins = [2, 5], amount = 3
Output: -1
Explanation: Repeated values 2 and 5 cannot produce an exact total of 3.
Recursion
Each denomination creates a simple choice. Skipping the current denomination moves to smaller denominations, while taking the current denomination reduces the remaining amount and keeps the same denomination available. Keeping the same index after a take captures the unlimited supply rule.
State solve(index, remaining) returns the fewest coins needed from denominations 0 through index. The initial call uses (n - 1, amount) because the full denomination list and complete target must remain available at the beginning.
Algorithm
Begin with state
(n - 1, amount)because the complete denomination list must build the original target.Handle index
0through divisibility because repeated copies of the first denomination provide the only remaining possible construction.Explore the skip branch with
(index - 1, remaining)because excluding the current denomination leaves the required amount unchanged.Keep the take branch at infinity until the current denomination fits because an oversized coin cannot belong to an exact positive remainder.
Explore the take branch with
(index, remaining - coins[index])because unlimited supply keeps the current denomination available.Add one only after the smaller take state is valid because an impossible remainder must never become a valid candidate.
Return the smaller branch count because the required combination uses the fewest coins among every valid pick-or-skip path.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: int infinity = 1000000000; // Finds the minimum count for one DP state. int solve( int index, int remaining, vector<int>& coins ) { // The first coin must divide the remainder. if (index == 0) { // Exact division creates a valid construction. if (remaining % coins[0] == 0) { return remaining / coins[0]; } return infinity; } // Skipping moves to smaller denominations. int notTaken = solve(index - 1, remaining, coins); int taken = infinity; // Taking is valid only inside the remainder. if (coins[index] <= remaining) { // Reuse keeps the current index available. int smaller = solve( index, remaining - coins[index], coins ); // Only a valid smaller state accepts a coin. if (smaller != infinity) { taken = 1 + smaller; } } // The smaller count gives the best construction. return min(notTaken, taken); }public: // Returns the minimum coins for the target. int minimumCoins(vector<int>& coins, int amount) { int n = coins.size(); // The full list starts with the full target. int answer = solve(n - 1, amount, coins); // The sentinel marks an impossible target. if (answer == infinity) { return -1; } return answer; }};// Driver codeint main() { vector<int> coins = {1, 2, 5}; int amount = 11; Solution obj; cout << obj.minimumCoins(coins, amount); return 0;}Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.
Complexity Analysis
Time Complexity: O(2(N + amount / minCoin)), where N is the number of denominations, because each state can branch into skip and take choices across at most N + amount / minCoin recursive levels. Here, minCoin denotes the smallest denomination.
Space Complexity: O(N + amount / minCoin), because the deepest recursion path can contain denomination skips and repeated takes before reaching a base state. Here, minCoin denotes the smallest denomination.
Memoization
Many recursive paths reach the same pair of index and remaining amount. A dp table stores each completed state, so later visits can reuse an answer instead of rebuilding the same recursion tree.
State meaning and branch logic remain unchanged. Only a cache check before recursion and a cache write after the minimum calculation are added.
Algorithm
Begin with a
dptable of sizenbyamount + 1, filled with-1, so every untouched cell marks an uncalculated state.Start from
(n - 1, amount)because the complete denomination list must still form the full target.Handle index
0through divisibility because only repeated copies of the first denomination remain available.Return
dp[index][remaining]after a cache hit because the same state always has the same minimum count.Explore the unchanged skip and take branches because memoization must preserve the recursive state meaning.
Store the smaller valid branch count in
dpbecause later paths can avoid rebuilding the same state.Convert the infinity sentinel to
-1at the public boundary because the required output uses-1for an impossible target.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: int infinity = 1000000000; // Finds and stores one minimum-count state. int solve( int index, int remaining, vector<int>& coins, vector<vector<int>>& dp ) { // The first coin must divide the remainder. if (index == 0) { // Exact division creates a valid construction. if (remaining % coins[0] == 0) { return remaining / coins[0]; } return infinity; } // A stored state avoids repeated recursion. if (dp[index][remaining] != -1) { return dp[index][remaining]; } // Skipping moves to smaller denominations. int notTaken = solve( index - 1, remaining, coins, dp ); int taken = infinity; // Taking is valid only inside the remainder. if (coins[index] <= remaining) { // Reuse keeps the current index available. int smaller = solve( index, remaining - coins[index], coins, dp ); // Only a valid smaller state accepts a coin. if (smaller != infinity) { taken = 1 + smaller; } } // The cache stores the smaller branch count. dp[index][remaining] = min(notTaken, taken); return dp[index][remaining]; }public: // Returns the minimum coins for the target. int minimumCoins(vector<int>& coins, int amount) { int n = coins.size(); // Negative one marks every uncalculated state. vector<vector<int>> dp( n, vector<int>(amount + 1, -1) ); // The full list starts with the full target. int answer = solve( n - 1, amount, coins, dp ); // The sentinel marks an impossible target. if (answer == infinity) { return -1; } return answer; }};// Driver codeint main() { vector<int> coins = {1, 2, 5}; int amount = 11; Solution obj; cout << obj.minimumCoins(coins, amount); return 0;}Complexity Analysis
Time Complexity: O(N × amount), where N is the number of denominations, because at most N × (amount + 1) states are calculated once, with constant-time skip, take, and minimum operations per state.
Space Complexity: O(N × amount + N + amount / minCoin), because the dp table stores all states, while the recursion stack can grow through skipped denominations and repeated takes of the smallest denomination. Here, minCoin denotes the smallest denomination.
Tabulation
Tabulation evaluates the same states from smaller indices and smaller amounts upward. The first row handles repeated copies of the first denomination, and every later row compares skipping the current coin with taking the current coin again.
An increasing amount order keeps dp[index][value - coins[index]] ready inside the current row. The current-row reference preserves unlimited reuse, while the previous-row reference represents a skip.
Algorithm
Begin with an
nbyamount + 1table filled with infinity so unreachable sums cannot win a minimum comparison.Fill the first row through divisibility because only repeated copies of
coins[0]can form first-row amounts.Process denomination rows from index
1upward because every skip transition needs the completed previous row.Process amounts from
0throughamountbecause every take transition needs a smaller amount from the current row.Read
dp[index - 1][value]for the skip count because excluding the current denomination moves to the preceding row.Read
dp[index][value - coins[index]]for a valid take because unlimited supply keeps the current row active.Store the smaller branch count and convert the final infinity value to
-1because only exact constructions qualify.
Dry Run
Minimum Coin Tabulation
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the minimum coins for the target. int minimumCoins(vector<int>& coins, int amount) { int n = coins.size(); int infinity = 1000000000; // Infinity marks every unreachable state. vector<vector<int>> dp( n, vector<int>(amount + 1, infinity) ); // Divisible amounts use only the first coin. for (int value = 0; value <= amount; value++) { // Exact division creates a valid construction. if (value % coins[0] == 0) { dp[0][value] = value / coins[0]; } } // Each row adds one available denomination. for (int index = 1; index < n; index++) { // Ascending amounts allow current-coin reuse. for (int value = 0; value <= amount; value++) { // The previous row represents a skip. int notTaken = dp[index - 1][value]; int taken = infinity; // Taking is valid only inside the amount. if (coins[index] <= value) { int smaller = dp[ index ][value - coins[index]]; // Only a valid smaller state accepts a coin. if (smaller != infinity) { taken = 1 + smaller; } } // Both branch counts define the current state. dp[index][value] = min( notTaken, taken ); } } int answer = dp[n - 1][amount]; // The sentinel marks an impossible target. if (answer == infinity) { return -1; } return answer; }};// Driver codeint main() { vector<int> coins = {1, 2, 5}; int amount = 11; Solution obj; cout << obj.minimumCoins(coins, amount); return 0;}Complexity Analysis
Time Complexity: O(N × amount), where N is the number of denominations, because every row processes all amount + 1 target values once.
Space Complexity: O(N × amount), because the two-dimensional dp table stores one minimum count for every denomination-and-amount state, with no recursion stack.
Space Optimization
Each tabulation state reads a skip value from the previous row and a smaller take value from the current row. Rows older than the previous row never contribute to a new state, so the full table can shrink to two arrays.
Array previous represents the completed row before the current denomination. Array current is calculated from left to right, then the completed current row becomes previous for the next denomination.
Algorithm
Begin with
previousfilled with infinity so unreachable amounts remain excluded from minimum comparisons.Fill
previousthrough divisibility because the first denomination alone defines the first conceptual DP row.Create a fresh
currentrow for every later denomination so stale values cannot leak across denomination states.Process amounts in increasing order because taking the current denomination reads an already calculated smaller amount from
current.Compare
previous[value]with1 + current[value - coins[index]]because the two values represent skipping and taking the denomination.Store the minimum in
current[value], then assign the completed row topreviousbecause the next denomination needs only the newest results.Return
previous[amount]or-1after the sentinel remains because the final rolling row represents the complete denomination list.
Dry Run
Minimum Coin Space Optimizaiton
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the minimum coins for the target. int minimumCoins(vector<int>& coins, int amount) { int n = coins.size(); int infinity = 1000000000; // Infinity marks unreachable first-row amounts. vector<int> previous(amount + 1, infinity); // Divisible amounts use only the first coin. for (int value = 0; value <= amount; value++) { // Exact division creates a valid construction. if (value % coins[0] == 0) { previous[value] = value / coins[0]; } } // Each pass builds the next denomination row. for (int index = 1; index < n; index++) { vector<int> current(amount + 1, infinity); // Ascending amounts allow current-coin reuse. for (int value = 0; value <= amount; value++) { // The previous row represents a skip. int notTaken = previous[value]; int taken = infinity; // Taking is valid only inside the amount. if (coins[index] <= value) { int smaller = current[ value - coins[index] ]; // A valid smaller state accepts a coin. if (smaller != infinity) { taken = 1 + smaller; } } // Current keeps the best of both choices. current[value] = min(notTaken, taken); } // Shift the finished row into previous. previous.swap(current); } int answer = previous[amount]; // The sentinel marks an impossible target. if (answer == infinity) { return -1; } return answer; }};// Driver codeint main() { vector<int> coins = {1, 2, 5}; int amount = 11; Solution obj; cout << obj.minimumCoins(coins, amount); return 0;}Complexity Analysis
Time Complexity: O(N × amount), where N is the number of denominations, because every denomination processes all amount + 1 target values once.
Space Complexity: O(amount), because only the previous and current arrays of length amount + 1 are kept in memory.
Interview follow-up Questions
No. For coins = [1, 3, 4] and amount = 6, greedy selection uses [4, 1, 1], while optimal selection uses [3, 3].
Be the first to add a comment.