Leetcode 518. Coin Change II

In this post, solution to leetcode problem – 518, coin change II – is explained. Please refer to this link for detail problem description.

This is very similar to combination sum IV problem. The only difference is that the order doesn’t matter and this is essentially a subset problem with duplicates. Let’s see how we can approach the problem.

Brute Force

Exhaustively enumerate all subsets and check if it makes the amount. This will have exponential cost.

Optimized version

We can follow the similar approach as combination sum IV problem. The only difference is that order doesn’t matter and if you blindly add results from previous coins, you will end up counting the duplicate as you see in the diagram below.

In the above diagram, the recurrence relation is simply adding the results from previous amount with all the coin denominations. How can we avoid counting the duplicate? Instead of looking at all the coins for each amount, we can control how many coins each node has. For example, each node is responsible for keeping track of the number of coins for only one coin. Let’s look at the diagram below.

Now, it is not counting the duplicate and you just need to add up all the nodes with valid combinations to get the final result. The recurrence relation would be f(i, a) = sum(f(i-1, a – c*coins[i])) where i is coin index, a is amount, c is number of coins. The range for c is 0 to max coins. How do you calculate max coin? It is simply amount / coins[i]. As there are overlapping subproblems, we can use dynamic programming to solve this. For this, as there are two variables, we would need two dimensional array. row represents coin index and col represents amount. (you can change row/col if you want). What’s the base case? For the first column, when amount = 0, there is only one combination to make the amount – empty subset. For the first row, when no coins are used – I remember I said row is coin index, but since index makes problem slightly more difficult, let’s say row is ith coin that 0th coin means no coin, and the first coin is the first coin in coins – there isn’t any combination possible to make any amount. So everything is 0 except the first column. Although there are more optimizations possible, let’s take a look at the pseudo-code

table: 2d array of row (num coins + 1) col (amount + 1)
initialze first column to 1. everything else is 0

for i in 1 to n: // n is number of coins
    for a in 1 to amount:
        maxCoins = a / coins[i-1]  // note that i is index of table. to access corresponding coin, need to subtract 1
        // check all the possible number of coins can be included
        for c in 0 to maxCoins:
            table[i][a] += table[i-1][a - c*coins[i-1]]
            
return table[n][amount]

Solution is very simple but look at the time complexity. We already have a 2D table and there is an additional for-loop for each cell in the table. Can we do better?

More optimized version

If you closely look at the code, we can eliminate the inner for-loop (c) while achieving the goal. Instead of checking possible number of coins in the for-loop, let’s look at from exclusion/inclusion point of view. At each amount and coin[i], we have a choice – exclude or include. If you exclude, then you check the next coin. If you include, you have another choice – exclude or include the same coin again.

With that, we have a better time complexity. Here is the code written in C++.

int change(int amount, vector<int>& coins) {
    vector<vector<int>> table(coins.size()+1, vector<int>(amount+1, 0));
    for (int i = 0; i <= coins.size(); ++i)
    {
        table[i][0] = 1;
    }

    for (int i = 1; i <= coins.size(); ++i)
    {
        for (int j = 1; j <= amount; ++j)
        {
            // exclude
            table[i][j] = table[i-1][j];

            // include
            if (j >= coins[i-1])
            {
                table[i][j] += table[i][j-coins[i-1]];    
            }
        }
    }
    
    return table[coins.size()][amount];
}

Time complexity=O(n*amount) where n is length of coins and amount is initial amount. Space complexity=(n*amount) because we create 2D array of n*amount. We are very close but there is one more optimization we can achieve – space complexity. If you look at the all the update, exclude code at line 13 is completely unnecessary because after processing the row, next row can start exactly same as previous row. In addition to that, when you look at inclusion code at line 18, you only look at previous column because you are including the same coin!

It means that we only need a 1D array. Here is the C++ code.

int change(int amount, vector<int>& coins) {
    vector<int> table(amount+1, 0);
    table[0] = 1;

    for (int i = 1; i <= coins.size(); ++i)
    {
        for (int j = 1; j <= amount; ++j)
        {
            if (j >= coins[i-1])
            {
                table[j] += table[j-coins[i-1]];
            }
        }
    }
    
    return table[amount];
}

Time complexity is unchanged because you have to iterate all the coins with all the amount. However, we reduced the space complexity to O(amount).

Leetcode 377. Combination Sum IV

This post explains how to solve leetcode 377. combination sum IV problem. It starts with brute force idea and optimize to efficiently solve the problem. Please refer to this link for problem detail.

In this problem, you have two arguments – target and nums array. You are supposed to find the number of combinations to make the target amount only using numbers in nums array. In this problem, the order matters as you see in the example.

Let’s think about brute force idea – enumerate all the possible subsets of nums array. For each subset, you also need to check how many of each number can make the target. This is very expensive with exponential time complexity.

Can we do better? Let’s suppose nums = [1,2,3] and target is 10. Now, let’s also suppose that we have collected a number of combinations right before 10. In other words, we have the result at 9, 8, 7 which are (10 – 1), (10 – 2), (10 – 3). Since the order matters, we need to count all three cases. Then, the answer would be result(10 – 1) + result(10 – 2) + result(10 – 3). We can recursively derive the same relationship for 9, 8, 7 values. Let’s take a look at the below diagram.

We just need to recursively look for children until the base case is reached, which is 0. This is better than enumerating all the subsets and finding combinations. However, there is still room to improve because there are overlapping subproblems. This overlapping subproblem is like calculating fibonacci number recursively. We prevent calculating the same subproblem by storing the result. If subproblem is found, then we just need to reuse that one. Ultimately this becomes dynamic programming.

There are two ways – bottom up, top down – to solve the problem. In this post, I will just explain bottom up approach.

Let’s define f(t) as “number of combinations based on number in nums at target amount t”

Subsequently, the recurrence relation would be f(t) = sum(f(t – nums[i])), where i is 0..nums.length() (index). If t – nums[i] < 0, then it would be 0 as you can’t have negative value.

With the recurrence relation clearly defined, the code becomes very simple. The solution is based on C++.

Base case is t=0. There is only 1 way to make amount 0 which is empty subset. Based on the base case, we need to build up from the bottom until reach the target amount.

int combinationSum4(vector<int>& nums, int target) {
    vector<unsigned int> table(target+1);
    table[0] = 1;
    for (int i = 0; i <= target; ++i)
    {
        for (int num : nums)
        {
            if (i >= num)
            {
                table[i] += table[i-num];
            }
        }
    }

    return table[target];
}

The time complexity is O(nt) where n is length of nums and t is target amount. One gotcha is that if t is really large (ex. > 2^n) this essentially becomes same as brute force solution.

Intro to dynamic programming

This article is a simple intro to dynamic programming. Dynamic programming is typically considered the hardest algorithm to work with. However, there is a systematic way to solve the problem and we just need to practice based on that method.

Dynamic programming is best suited for the situation that needs to eliminate duplicate computations by caching it. Now let’s take a look at what steps are necessary to solve the problem.

Steps to solve DP

  • Define the state
  • List out all the state transitions
  • Implement a recursive solution
  • Memoize (top-down)
  • Make it bottom-up

Define the state

What are states in a dynamic programming context?

States are a set of parameters that define the system. Basically, we are trying to find the least number of parameters that change the state of the system. These are the inputs you are passing into the recursive function. Most of the time, it is just one or two parameters that define the state of the system.

After you define the state, you need to define the cost function and its return. It is the one we are trying to optimize for.

Example – knapsack problem

Provided a set of items, each with a weight and a value, determine the combination of each item to include in a bag so that the total weight is less than or equal to a given limit while having the largest total value possible.

states:
1. W – Available capacity of the back (limit)
2. i – Index of the item being considered

Cost function: knapsack(W, i), returns the largest total value that is less than or equal to the limit

Define the state transitions and optimal choice

At this step, you need to find out how the recurrence relation would be and what parameters you will pass to the recursive function. And how do we combine the result?

In order to find out the recurrence relation, you first need to identify the base cases.
1. very last state, where there are no more items to process.
2. some parameters are 0 or reached a final value that we are not able to proceed further.

After identifying the base cases, we need to define transitions. We need to identify all the valid candidates and try each of them one at a time (backtracking). Then, change parameters based on selected candidates and call recursive function. After trying all the candidates, the results need to be combined to find the optimal value we want to return.

Example – knapsack problem

Base cases:
1. If W = 0, it means the knapsack is full. Don’t have enough space for additional items.
2. If i = -1 (starting from last to 0), we processed all the items and nothing is left.
In those cases, the function returns 0

Transitions:
At each item, we have two decisions to make.
1. Take i-th item in the knapsack, then W will become W – weight[i]. It means weight[i] <= W must be true.
2. Skip the i-th item, and W remains the same.

This is the recurrence relation you see.

                                knapsack(W, i)
                                /           \
value[i] + knapsack(W - weight[i], i-1)      knapsack(W, i-1)
    
then, optimal choice would be:
max(value[i] + knapsack(W - weight[i], i-1), knapsack(W, i-1))


Recurrence relation
Base cases:
knapsack(0, i) = 0
knapsack(W, -1) = 0

if weight[i] <= W
    knapsack(W, i) = max(value[i] + knapsack(W - weight[i], i - 1), knapsack(W, i - 1))
else
    knapsack(W, i) = knapsack(W, i - 1)

Implement a recursive solution

This is python version but should be easy enough to understand.

def knapsack(W, i, weights, values):
    if W == 0 or i == -1:
        return 0
    if weights[i] <= W:
        return max(
            values[i] + knapsack(W - weights[i], i - 1, weights, values),
            knapsack(W, i - 1, weights, values)
        )
    else:
        return knapsack(W, i - 1, weights, values)

Memoize (top-down)

The naive recursive solution is slow – O(2^n) – and we can improve the performance by using memoization. How do we use it?
We cache the results of subproblems to avoid computing duplicate subproblems.

If there is only one parameter, we can use a 1D array and use the value of the parameter as the index to store the result.
If there are two parameters, then we use a 2D array – matrix.
Please note to initialize the array with default values.

def knapsack(W, i, weights, values, dp):
    if W == 0 or i == -1:
        return 0
    # check the dp to avoid duplicate computation
    if dp[W][i] != -1:
        return dp[W][i]
        
    # not computed yet
    result = None
    if weights[i] <= W:
        result = max(
            values[i] + knapsack(W - weights[i], i - 1, weights, values, dp),
            knapsack(W, i - 1, weights, values, dp)
        )
    else:
        result = knapsack(W, i - 1, weights, values, dp)
    
    dp[W][i] = result
    return result

Now you completed a dp problem with top-down approach.

Bottom up

If we already completed the problem, why do we even need to solve it bottom up?
There can be a couple of reasons to do that.
1. You might get stack overflow error due to many recursive calls
2. Bottom up is faster than top-down

In bottom-up approach, you have to think in the reverse direction. You need to start at the leaf/bottom of the tree, solve all the problems starting from the leaves and make the way up. It means we will start with the base case and compute upward to final state. We use one for loop for each parameter and fill all the values in the table by solving smaller problems into big ones.

Now, we need to decide which problem to solve first. It actually depends on how the parameters change in recurrence relation. If the parameter decreases in the subproblem then we start from 0 and go all the way up to the maximum value of the parameter.

Base case
if i = 0, return 0
if w = 0, return 0

Bottom up equation
dp[w][i] = max(values[i] + dp[w-weight[i]][i], dp[w][i-1])
def knapsack(W, weights, values):
    dp = [[0 for i in range(0, len(weights) + 1)] for j in range(0, W + 1)]
    for i in range(1, len(weights) + 1):
        for w in range(0, W + 1):
            if weights[i-1] <= w:
                dp[w][i] = max(dp[w]][i-1], dp[w-weights[i-1]][i-1] + values[i-1])
            else:
                dp[w][i] = dp[w][i-1]
    return dp[W][len(weights)]

At first glance, bottom-up solution doesn’t look intuitive at all. However, after solving top-down and defining proper equation it totally makes sense. Dynamic programming is hard but you will definitely get better by practicing!