Coin Change II

Problem

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the number of distinct combinations that total up to amount. If it’s impossible to make up the amount, return 0.

You may assume that you have an unlimited number of each coin and that each value in coins is unique.

Examples

Example 1:

Input: amount = 4, coins = [1,2,3]

Output: 4

Explanation:

• 1+1+1+1 = 4
• 1+1+2 = 4
• 2+2 = 4
• 1+3 = 4

Example 2:

Input: amount = 7, coins = [2,4]

Output: 0

Constraints

• 1 <= coins.length <= 100
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000

You should aim for a solution as good or better than O(n * a) time and O(n * a) space, where n is the number of coins and a is the given amount.

Solution

A regular DFS with memorization would loop over all possible next coins. But here we need to be careful about double counting permutations. So we make the invariant be the number of ways to make the remaining amount, but we can only pull from a subset of the coins starting from the start_idx. We then have 2 choices in the loop: use the current coin and recurse, or skip the coin.

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        const int NUM_COINS = coins.size();
        std::vector<std::vector<int>> memo(
            NUM_COINS, std::vector<int>(amount + 1, -1)
        );
 
        // Number of ways to make remaining, only using coins
        // from start_idx onwards
        std::function<int(int, int)> dfs;
        dfs = [&](int remaining, int start_idx) -> int {
            // Successfully made the amount
            if (remaining == 0) { return 1;}
            // No coins left, or overshot the amount
            if (start_idx == NUM_COINS || remaining < 0) { return 0; }
            // Seen this result before
            if (memo[start_idx][remaining] != -1) { 
                return memo[start_idx][remaining]; 
            }
 
            // Choise 1: use coins[start_idx], and stay at i because 
            //           we can reuse that coin
            int use = dfs(remaining - coins[start_idx], start_idx);
            // Choice 2: skip coins[start_idx] and move to next coin
            int skip = dfs(remaining, start_idx + 1);
 
            memo[start_idx][remaining] = use + skip;
            return memo[start_idx][remaining] ;
        };
        return dfs(amount, 0);
    }
};