DSA

Coin Change II

Covers: Recursive Version, Memoized Version, Tabulation:. Optimal — Time O(n*A), Space O(n*A).

August 8, 2026

DSA Dynamic Programming DP LeetCode Practice

Practice Link

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

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

The answer is guaranteed to fit into a signed 32-bit integer.

Recursive Version#

For each coin at index n we either skip it (move to n-1 with the same amount) or use it (subtract its value and stay at the same index, since we have infinite supply). We count combinations — not permutations — so "skip" always moves to the next coin, preventing duplicates. The base case amount == 0 means we found a valid combination. Without caching, overlapping sub-problems cause exponential time.

cpp

class Solution {
public:
    int changeUtil(int amount, int n, vector<int>&coins)
    {
        if(amount==0)
            return 1;
        if(n<0)
            return 0;

        int res = changeUtil(amount, n-1, coins);
        if(coins[n]<=amount)
            res += changeUtil(amount-coins[n], n, coins);

        return res;
    }

    int change(int amount, vector<int>& coins) {
        return changeUtil(amount, coins.size()-1, coins);
    }
};

Time Complexity: O(2^n), -> TLE

Space Complexity: O(n)

Memoized Version#

Cache results in a 2D table memo[amount][coinIndex]. Because the same (amount, n) pair is reached via many different use sequences, memoization cuts the repeated work from exponential down to O(n*A) unique states, each computed once. The recursive call stack still contributes O(n) overhead.

cpp

class Solution {
public:
    int changeUtil(int amount, int n, vector<int>&coins, vector<vector<int>> &memo)
    {
        if(amount==0)
            return 1;
        if(n<0)
            return 0;

        if(memo[amount][n]!=-1)
            return memo[amount][n];

        int res = changeUtil(amount, n-1, coins, memo);
        if(coins[n]<=amount)
            res += changeUtil(amount-coins[n], n, coins, memo);

        return memo[amount][n] = res;
    }

    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> memo(amount+1, vector<int>(n,-1));
        return changeUtil(amount, coins.size()-1, coins, memo);
    }
};

Time Complexity: O(n*A), where A -> amount

Space Complexity: O(n*A) +O(n)

Tabulation#

Build the answer iteratively. dp[i][j] = number of ways to make amount i using the first j coin types. Base case: dp[0][j] = 1 for all j (one way to make amount 0 — use no coins). We fill row by row: skip coin j gives dp[i][j-1]; use coin j (if it fits) adds dp[i - coins[j-1]][j] (same j because coins are reusable). This eliminates recursion overhead while keeping O(n*A) time and space.

cpp

class Solution {
public:
    int changeUtil(int amount, int n, vector<int>&coins)
    {
        vector<vector<int>> dp(amount+1, vector<int>(n+1,0));

        for(int i=0;i<=n;i++)
            dp[0][i] = 1;

        for(int j=0;j<=amount;j++)
            dp[j][0] = 0;

        for(int i=1;i<=amount;i++)
        {
            for(int j=1;j<=n;j++)
            {
                long long not_take= dp[i][j-1];
                long long take = 0;
                if(coins[j-1]<=i)
                    take += dp[i-coins[j-1]][j];

                dp[i][j] = take + not_take;
            }
        }
        return dp[amount][n];
    }

    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        return changeUtil(amount, coins.size(), coins);
    }
};

Time Complexity: O(n*A), where A -> amount

Space Complexity: O(n*A)

DSALongest Common Prefix5 approaches incl. Horizontal Scanning, Vertical Scanning, Binary Search, and more. Optimal — Time O(s log m), Space O(1).DSAMaximum Subarray SumCovers: Brute Force, Optimal. Optimal — Time O(n), Space O(1).DSAPalindromic SubstringCovers: Brute Force: generate all su…, Expansion on center, DP. Optimal — Time O(n<sup>2</sup>), Space O(n<sup>2</sup>).

Recursive Version#

Memoized Version#

Tabulation#

Related articles