You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:
Input: amount = 10, coins = [10]
Output: 1

Note:
You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

This is one variant of the classic knapsack problem where you can use unlimited items of a kind. The target is to find the total number of combinations. Another similar problem is to find the shortest combination: Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm

Unlimite Knapsack Problem via Depth First Search Algorithm to Find All Combination

The most intuitive method is to use the Depth First Search algorithm that makes a choice (choose a coin) and move on to the next by subtracting the coin value from the amount, thus, we have a smaller problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        dfs(amount, coins, 0);
        return ans;
    }
private:
    int ans = 0;
    void dfs(int amount, vector<int>& coins, int idx) {
        if (amount == 0) {
            ans ++;
            return;
        }        
        for (int i = idx; i < coins.size(); ++ i) {
            if (amount >= coins[i]) {
                // choose coins[i] and solve a smaller problem recursively
                dfs(amount - coins[i], coins, i);
            }
        }
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        dfs(amount, coins, 0);
        return ans;
    }
private:
    int ans = 0;
    void dfs(int amount, vector<int>& coins, int idx) {
        if (amount == 0) {
            ans ++;
            return;
        }        
        for (int i = idx; i < coins.size(); ++ i) {
            if (amount >= coins[i]) {
                // choose coins[i] and solve a smaller problem recursively
                dfs(amount - coins[i], coins, i);
            }
        }
    }
};

We recursively solve a smaller problem and when the amount is reduced to zero, we can increment the answer. The problem with above C++ DPS recursive implementation is that the intermediate smaller problems are computed again and again, which leads to exponential complexity O(N^N) where N is the number of the coin values.

Solving the Unlimited Knapsack Combination via Dynamic Programming

dynamic-programming-interview-questions

We can use the F(N) to represent the number of combinations for amount N, then following DP equation applies:

1
2

f[0] = 1; // for zero amount, only 1 combination which is 0.
f[n] = sum(F[N-c]); // c - the coin values.

f[0] = 1; // for zero amount, only 1 combination which is 0.
f[n] = sum(F[N-c]); // c - the coin values.

As such, the intermediate results are remembered in the F array, and the complexity is O(NM) where N is the number of different items e.g. coins, and the M is the amount e.g. the total capacity for the knapsack. The below C++ uses O(M) additional space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (const auto &c: coins) {
            for (int i = 1; i <= amount; ++ i) {
                if (i >= c) {
                    f[i] += f[i - c];
                }
            }
        }
        return f[amount];
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> f(amount + 1, 0);
        f[0] = 1;
        for (const auto &c: coins) {
            for (int i = 1; i <= amount; ++ i) {
                if (i >= c) {
                    f[i] += f[i - c];
                }
            }
        }
        return f[amount];
    }
};

–EOF (The Ultimate Computing & Technology Blog) —