Good day gals and guys. It is a nice Monday morning in the Twin Cities of Minneapolis and St. Paul. Believe it or not but the high temperatures in the mid to upper 90s F that we have been getting for the past two weeks this Spring has changed in the forecast for the last 10 days of Spring 2021. The forecast call for highs in the upper 70’s to low 80’s F which represents on average a 20F degree reduction. One way or the other, unless it is raining, my wife and I are planning of getting up before 06:00 AM, having breakfast and then heading out for a daily walk. It seems that every day there are more people out and about early in order to avoid the heat in the afternoon.
Our weekend was uneventful. We walked, chatted with people, and prepared food in the grill. Yesterday we made fish and chips in the grill. We want to master the technique because frying potatoes and fish indoors unnecessarily heats the house and leaves food odors that tend to last for a couple hours after we are done consuming lunch. That said, at work and personal life, the only way to learn and become efficient with different tasks is to read, practice, get feedback, make modifications and repeat! In addition you must like what you do; otherwise it is very difficult to improve.
I continue to install applications on my new iPhone. Hopefully this week I will be done installing some Google apps and hopefully getting the data into the iPhone.
I also continue watching the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. I could have watched the video in five hours but without experimenting and writing posts in this blog, the gains would have been reduced.
Write a function`howSum(targetSum, numbers)` that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null. If there are multiple combinations possible, you may return any single one.
We have seen this problem before and were able to generate a solution as illustrated by the How Sum post. At the time we used dynamic programming and memoization. This time we will use the tabulation technique.
long[] howSum(int targetSum, int[] numbers) {
}
The instructor in the YouTube video uses JavaScript on a Macintosh laptop to solve the problem. I am using Java and the VSCode IDE on a Windows computer. Given that Java is so ubiquitous, you should not encounter issues with the alternate programming language that I chose.
The signature for the function in question is simple. We are given a target sum and an array of integers. We must return any combination of numbers that add to the specified target sum value.
0 1,2,3,4 main <<< targetSum: 0 main <<< numbers: [1, 2, 3, 4] main <<< howSum: null main <<< time: 3 micro seconds 7 5,3,4 main <<< targetSum: 7 main <<< numbers: [5, 3, 4] <<< table: [[], null, null, [3], [4], [5], [3, 3], null] <<< table: [[], null, null, [3], [4], [5], [3, 3], [3, 4]] main <<< howSum: [3, 4] main <<< time: 1204 micro seconds 7 2,3 main <<< targetSum: 7 main <<< numbers: [2, 3] main <<< howSum: [2, 2, 3] main <<< time: 480 micro seconds 7 5,3,4,7 main <<< targetSum: 7 main <<< numbers: [5, 3, 4, 7] main <<< howSum: [3, 4] main <<< time: 1058 micro seconds 7 2,4 main <<< targetSum: 7 main <<< numbers: [2, 4] main <<< howSum: null main <<< time: 92 micro seconds 8 2,3,5 main <<< targetSum: 8 main <<< numbers: [2, 3, 5] main <<< howSum: [3, 5] main <<< time: 547 micro seconds 300 7,14 main <<< targetSum: 300 main <<< numbers: [7, 14] main <<< howSum: null main <<< time: 192 micro seconds
The instructor makes use of a set of test cases. I believe they are all covered here plus a few that I used to get additional verifications on the correctness of the solution.
Our test code reads the first two input lines. The first line contains the value for the target sum and the second the values for the numbers array.
After populating the proper values the variables are displayed to make sure we have not introduced an issue.
The result of the function of interest is displayed. On the next and final line we display the time the function took to execute.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
long start = 0;
long end = 0;
int[] ans = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read target sum ****
int targetSum = Integer.parseInt(br.readLine().trim());
// **** read numbers ****
int[] numbers = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< targetSum: " + targetSum);
System.out.println("main <<< numbers: " + Arrays.toString(numbers));
// **** call function of interest ****
start = System.nanoTime();
ans = howSum(targetSum, numbers);
end = System.nanoTime();
// ???? ????
System.out.println("main <<< howSum: " + Arrays.toString(ans));
System.out.println("main <<< time: " + ((end - start) / 1000) + " micro seconds");
}
The actual test code is quite simple and seems to match the description of the test cases. Not much to add at this time.
**** Tabulation Recipe **** 1. Visualize the problem as a table 2. Size the table based on the inputs 3. Initialize the table with some values 4. Seed the trivial answer into the table 5. Iterate through the table 6. Fill further positions based on the current position
Our tabulation recipe calls for visualizing the problem as a table. This is the hardest part to solve the problem.
+------+------+------+------+------+------+------+------+ | [] | null | null | [3] | [4] | [5] | null | null | +------+------+------+------+------+------+------+------+ 0 1 2 3 4 5 6 7
Let’s take a look at the second test case (the one with targetSum: 7 and numbers: [5, 3, 4]).
We have a set of numbers and we must find a combination that adds up to 7. We define an array of array lists with 8 entries. We then initialize the array (table) with null values. Since we can return an empty list with any set of numbers we initialize the first entry with an empty list.
If you look at our recipe, we have taken care of the first four steps.
We now need to iterate through the table using the values in the numbers array populating the different lists as needed. Of special interest is the last entry in our table because it matches to the target sum which in this case is 7.
Note that we have done some other initializations in our table. Let’s ignore them until we take a look at the code for the function of interest.
numbers: [5, 3, 4]
+------+------+------+------+------+------+-------+------+
| [] | null | null | [3] | [4] | [5] | [3,3] | null |
+------+------+------+------+------+------+-------+------+
0 1 2 3 4 5 6 7
| | | |
| | +--... |
| +---------... |
+---------------------+
After the initialization step, we look at entries 1 and 2 in the table. Since they are null we have nothing to contribute to the rest of the entries so we check and skip.
We finally get to table entry 3. Since we have a value [3] we look at the entries in the numbers array and try to find locations in the table in which we can add [3] to the current lists. The only location we can contribute to is 6 due to the fact that we can reach it and the index is in bounds.
numbers: [5, 3, 4]
+------+------+------+------+------+------+-------+-------+
| [] | null | null | [3] | [4] | [5] | [3,3] | [3,4] |
+------+------+------+------+------+------+-------+-------+
0 1 2 3 4 5 6 7
| | | |
| | +--... |
| +---------... |
+---------------------+
We now move to the fourth element in the table. We repeat the process that we will see in detail when we get to view the code for the function in question. This time we update the cell in the table at index 7. At that point we can exit due to the fact that the requirements call for a single combination.
/**
* Write a function`howSum(targetSum, numbers)` that takes in a
* targetSum and an array of numbers as arguments.
*
* The function should return an array containing any combination of
* elements that add up to exactly the targetSum.
*
* If there is no combination that adds up to the targetSum, then
* return null.
*
* If there are multiple combinations possible, you may return any
* single one.
*
* m = targetSum
* n = numbers.length
*
* Time: O(m^2 * n) - Space: O(m^2)
*/
static int[] howSum(int targetSum, int[] numbers) {
// **** sanity checks ****
if (targetSum == 0) return null;
/ **** initialization (Java(16777748)) ****
@SuppressWarnings("unchecked")
ArrayList<Integer>[] table = new ArrayList[targetSum + 1];
table[0] = new ArrayList<Integer>();
for (int i = 0; i < numbers.length; i++) {
ArrayList<Integer> al = new ArrayList<Integer>();
int nums = numbers[i];
al.add(nums);
table[nums] = al;
}
// **** iterate through the table ****
for (int i = 1; i <= targetSum; i++) {
// ???? ????
// System.out.println("<<< i: " + i);
// **** skip this entry (if needed) ****
if (table[i] == null)
continue;
// **** loop through the numbers array ****
for (int j = 0; j < numbers.length; j++) {
// **** for ease of use ****
int num = numbers[j];
// ???? ????
// System.out.println("<<< num: " + num);
// **** compute target index ****
int ndx = i + num;
// **** skip this index (out of range) ****
if (ndx > targetSum)
continue;
// ???? ????
// System.out.println("<<< ndx: " + ndx);
// **** initialize list (if needed) ****
if (table[ndx] == null)
table[ndx] = new ArrayList<Integer>();
// **** copy all elements from table[i] to table[ndx] ****
ArrayList<Integer> src = table[i];
ArrayList<Integer> dst = table[ndx];
dst.clear();
dst.addAll(src);
// **** add current element to table[ndx] ****
dst.add(num);
// ???? ????
// System.out.println("<<< dst: " + dst.toString());
// **** check if done ****
if (ndx == targetSum) {
// ???? ????
// System.out.println("<<< table: " + Arrays.toString(table));
// **** convert List<Integer> to int[] ****
int[] arr = dst.stream().mapToInt( x -> x).toArray();
// **** return int[] ****
return arr;
}
}
// ???? ????
// System.out.println("<<< table: " + Arrays.toString(table));
}
// **** check if no ansswer was found ****
if (table[targetSum] == null) return null;
// **** get last list in the table ****
ArrayList<Integer> lst = table[targetSum];
// **** convert List<Integer> to int[] ****
int[] arr = lst.stream().mapToInt( x -> x).toArray();
// **** return int[] ****
return arr;
}
This is the code for the function in question. Looking at the code we should be able to fully understand what are we doing and most important why.
We start by performing a sanity check. If the target sum equals 0 we return a null because there is no way to find elements that return a null combination.
To solve this problem we could use ArrayList<ArrayList<Integer>> which is not a table in the sense an array is. We could have used such data structure, but I decided to use ArrayList<Integer>[] which is to be avoided unless you know what you are doing. With such advice, I decided to stick to the array implementation.
Note that the declaration brings up a warning. To avoid it I just add the directive to suppress warnings and move forward.
The table (it is an array) has enough elements in order to facilitate operations. In this case we just declare a 1D table with target sum elements plus one.
All the entries in the table have null values. We need to initialize the first entry to an empty list because that is an end condition which always holds.
We then loop through the values in the numbers array. For each value we initialize a list with the specified value. Thinks of it as if you initialize list at index 5 with a list containing 5, is because if you want to include a 5 in your combination, a 5 must already be in the list.
Now we are ready to enter a loop that iterates through the initializes entries in the table.
If the entry in the table is null, we skip it. The reason being is that we do not have numbers that we can use to generate a value for that entry. For example, when we hit table entry 1, we cannot fund an entry in the numbers array that we can use to generate a 1. The same holds true for entry 2 in the table.
If we reach a table entry with a list, then we can use it to create other lists which will add up to numbers that are in our table. Note that in this example, if we reach an entry in the table that is out of bounds, we must skip it.
We need to compute the index in the table for the current number in the numbers array. If the resulting index is out of bounds we skip this entry.
Using a valid index we create a new empty list in the table. We populate it by copying the contents of the table at index I into the table at index ndx.
Once that is done, we add the value from the numbers array. If you look at the results, the values in this table should add up to the index holding the list. This makes sense. For example, if we are at index 6 then the sum of values in the associated list at index 6 in the table must add up to 6.
At this point we could continue looping. I decided to add the condition that checks if we filled in the table entry with the index that matches the target sum. This implies that we just built a list at index 7 in our table whose values add up to 7. Since we are required to return any combination we can exit. The code in the YouTube video continues to loop and that is OK. Sooner or later the loops will end and the result that we are searching will be found in the final list at the last entry in our table. If you have doubts, remove the check and let the code continue to loop. A list of numbers, which might differ from the ones encountered the first time such entry in the table is populated, will be located in the last table entry.
BTW, if you are interested in which was the exact warning I ran into by declaring the array of ArrayList, it follows:
Type safety: The expression of type ArrayList[] needs unchecked conversion to conform to ArrayList<Integer>[] Java(16777748)
Hope you enjoyed the problem. In my opinion, to become proficient in solving dynamic programming problems, you need to solve a good number and keep your skills fresh by continuing to solve them periodically.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John