At this point in the series, sufficient concepts and information about Dynamic Programming have been covered, such as optimal substructure, overlapping sub-problems, problem analysis and the techniques at arriving at the recurrence relation. From this point on, this series will pivot to applying those concepts and techniques to solve simple to more challenging Dynamic Programming problems.
In this blog, we will tackle the “Target Sum” Dynamic Programming problems using the top down approach.
Problem Statement
Given a target sum and an unsorted array of positive integers, we need to answer the following questions, and they are in the increasing order of complexity.
- Whether it is possible to generate the targetSum using the numbers in the array? — canSum(targetSum, integers)
- Return the number of possible combinations that add up exactly to the targetSum
- Return any combination of numbers that add up exactly to the targetSum. If there are multiple possible combinations, just return any of them — howSum(targetSum, integers)
- Return the shortest combination that adds up exactly to the targetSum, meaning it contains the fewest number of elements — bestSum(targetSum, integers)
We can assume the following:
- A number in the unsorted array can be used as many time as needed
- All the elements in the unsorted array are positive numbers
For example: if the targetSum is 8 and the integers are [2,3,5], then the following are the answers.
- canSum(8, [2,3,5]) => true, canSum(8, [3,6,9]) => false
- countSum(8, [2,3,5]) => 6
- howSum(8, [2,3,5]) => [2,2,2,2] (other combinations are [2,3,3], [3,5], etc)
- bestSum(8, [2,3,5]) => [3,5]
Problem Analysis:
- For the example above, given the targetSum value is in a single digit and the array size is less than the number of fingers on one’s hand, anyone with basic mathematics skills can easily determine that it is possible to come up with a combination [3,5]. However, if the targetSum value is in the million, our brain can’t easily come up with a combination. Let’s see how we can apply a systematic way of breaking the problem down to smaller ones and then identify the base case(s).
- We know we need to reduce the targetSum value down to smaller values, and all the way down to 0 if possible. If that is possible, then it means that there is a way to generate the targetSum using the numbers in the array. What are the available choices? We can reduce it down to smaller values by subtract it from each of the elements in the given array. Since we don’t know which path will lead us down to 0 value, then we will try them all.
- What we just established on the previous graph was a systematic way of reducing the targetSum value all the way down to the base cases — either 0 or less than 0. See the breakdown (recursion) tree in Figure #1 to gain deeper insights into how the breakdown happens recursively.
Problem Breakdown Tree:
Figure #1 provides a visual representation of reducing the given targetSum all the way down to the base cases. For each of the smaller values of the targetSum, we apply the same set of choices from the integer array.
There are two base cases. The problem breakdown stops when one of these base cases is reached.
- When targetSum is 0, which means there is a combination of numbers in the array that exactly adds up to it.
- When targetSum is less than 0, which means there is NOT a combination of numbers in the array that exactly adds up to it.
From Figure #1, a keen observer would see that there are many duplicate sub-problems, such as node with value 3,2,1 and so on.
canSum(targetSum, integers):
For the canSum(targetSum, integers) question, all we need to answer is whether it is possible to generate the targetSum using the numbers in the array, therefore we can stop the exploration once a valid combination is found, otherwise we will need to exhaustively perform the breakdown until all the base cases are reached.
Figure #2 shows we can stop the exploration the moment one valid combination is found. Therefore the execution would only explore the left most side of the tree and totally skip exploring the middle and right most of the tree.
canSum implementation:
Let’s see how we can translate this into a top down implementation, which recursively reduces the targetSum to one of the base cases.
- The two base cases are on line 7 and 11 (see Figure #3 below)
- The for loop on line 14 is the core logic for reducing the targetSum to smaller values by exploring the choices in the input array.
- Line 15 contains two important insights. The first one is reducing the targetSum by each element in the array and therefore it will get smaller and smaller as recursion goes deeper and deeper. The second one is the if condition, which stops the exploration if a smaller targetSum if canSumTopDown returns true.
- Line 21 return false when the exploration is exhausted and couldn’t find a combination that exactly adds up to the targetSum
canSum Complexity Analysis
- let m be the value of targetSum and let n be the array length
- In the worst case scenario, m is reduced by 1 at each level of the tree, therefore the recursion tree height will be m.
- For each level, in the worst case we need to explore every element in the array
- To deal with overlapping sub-problems, we use the cache to store the computations of targetSum value from 1 to targetSum, therefore there is no re-computation of same sub-problems
- The runtime complexity would be O(m * n)
- The space complexity is O(m), because a map data structure is allocated to hold the computations of targetSum value from 1 to targetSum
countSum(targetSum, integers):
The countSum(targetSum, integers) question is asking how many different combinations can be added up to the targetSum. The breakdown tree (recursion tree) Figure #1 above has the answer. Essentially where ever the leaf node with value of 0, it means that there is combination (from root to that leaf node) that exactly adds up to the targetSum. In Figure #1, we see 6 leaf nodes with value 0, so there are 6 different combinations in total.
The core logic for solving this question is quite similar to the one in canSum(targetSum, integers) problem. However, there are a few differences:
- We need to explore all possible combinations, therefore we can’t stop when one combination is found
- Instead of returning a boolean value, each of the base cases would return an integer. When there is a possible combination, the leaf node with value of 0 will return 1. When there is NOT a possible combination, the leaf node with a negative value will return 0.
- We need to maintain a count at each node in the tree, which adds up the count for each of the sub-trees. See Figure #4 for how the counts are bubbled up to the root node
countSum implementation:
The implementation of countSum is very similar to the canSum.
- The two base cases now return an integer to represent the count.
- Line 12 is an important one, it contains the total number of combinations at each particular node in the tree. The totalSum is incremented each time through the for loop
countSum Complexity Analysis
- The runtime and space complexity of countSum are identical to the ones in canSum
howSum(targetSum, integers):
The howSum(targetSum, integers) question is asking us to return a combination of integers that adds up to exactly the targetSum. From the countSum problem, we know that there might more than one combinations, this question is OK with any valid combination.
For example, for targetSum = 8 and integers = [2,3,5], any of the combinations below is considered a valid solution:
- [2,2,2,2], [2,3,3], [3,2,3], [3,3,2], [3,5], [5,3]
There are a few questions we need to think about:
- How do we know a particular integer is a part of a valid combination or not?
- How to store the combination of integers?
From examining the problem breakdown tree, we know there are two base cases. The one with a value of 0 in the the leaf node tells us there is a valid combination and the other one with value less than 0 tells us otherwise. Based on that information, we can return an appropriate signal for the upper node to determine what to do.
To put it more concretely:
- For the base case with a value of 0 in the the leaf node, we will return an empty list
- For the base case with a value less than 0 in the the leaf node, we will return null
howSum implementation:
There are a few differences in the implementation of this problem from the previous ones.
- The base case where the targetSum is 0, it will return an empty, which will be used by the upper nodes to store the combination
- The base case where the targetSum is less than 0, it will return null, which tells the upper nodes a particular integer is not a part of a valid combination
- Inside the for loop (line 15 to 19), it will determine whether to add a particular integer to the list based on the return object of the recursive call. Notice the exploration is stopped once it recognizes the return list is not null, which represents a valid combination was found. Before breaking out of the for loop, it adds the current integer to the list.
- It might a bit challenging to visualize this in your mind by just looking at the code. The recursion will go all the way down to one of base cases and then it will bubble up. I highly suggest that you walk through a example by using a pen and piece of paper to draw out the recursion tree yourself.
This implementation will return the first valid combination that it finds(if there are more than one) and the combination is built from the bottom up.
howSum Complexity Analysis
- The runtime and space complexity of howSum are identical to the ones in canSum
bestSum(targetSum, integers):
This question takes the complexity level up a notch from the howSum problem. Instead of any combination, this question asks for the best one, meaning the shortest one, in other words, the one that contains the least number of integers. If there is a tie for the shortest combination, it is OK to return one of those.
If we take a look at the node with value of 5 in the middle of level one in Figure #4, there are 3 possible combinations that add up exactly to 5, they are [2,3], [3,2], [5]. Among these, we would to pick the shortest one, which is [5].
bestSum implementation:
From the implementation perspective, as we explore each of the choices in the integer array, we need to maintain the shortest combination, and update it as a shorter one is found.
There are a few important and different steps in the code snippet below comparing to the one for howSum problem (see Figure #7 for the code)
- Before the “for loop” (line 14), we maintain to a variable to store the shortest combination. This variable is updated with a shorter one on line 20 if a shorter is found
- Line 18 controls when to update the list, only when the new combination is shorter than the current one. The condition (list == null) is for handling the case where it is the very first time in the for loop.
- For line 20 and 21, instead of updating it with a reference of a shorter combination, we need to create a new list, copy over the integers from the shorter list to the new list, and finally include the integer that we just explore. If we don’t make a copy of the list, we will get an incorrect result.
bestSum Complexity Analysis
- Let m be the value of targetSum and let n be the array length
- In the worst case scenario, we need to make a copy of tmpList (line 20) at every level of the problem breakdown tree and the maximum size of that list is m
- The runtime complexity would be O(m * n * m) => O(m² * n)
- For the space complexity, we are maintaining a map of integer to a list of integers, therefore the worst case scenario is O(m * m) => O(m²). The first m is for the number of entries in the map, and the second m is maximum size of each of the lists.
Summary
There you have it, we just went through four Dynamic Programming questions in the increasing order of complexity and with the same inputs.
We learned that drawing out the problem breakdown tree gives us a good visual model of how the recursion will play out. Then we identified the two base cases and figured out the appropriate value to return for each of them.
The exploration is driven by looping through the choices in the integer array. For the canSum and howSum problems, we figured out that it is OK to stop the exploration once a valid combination is found. However, the exploration needs to be exhausitve for the countSum and bestSum problems.
The problems covered in this blog are based on this awesome video from freeCodeCamp.org. If these problems intriguing to you, I highly recommend spending time to go through the video (it is 5 hours long, but totally worth it).
Resources:
- An excellent video about Dynamic Programming from freeCodeCamp.org. Highly recommended
- There is a lot of similarties between the Leetcode Coin Change problem and the above problems