It is the first Tuesday after the Memorial Day 2021. As I mentioned in a previous post I have been experiencing problems with my Pixel 4 phone. Apparently I purchased the phone less than two years ago. About a week ago the phone was working fine and suddenly it died. I tried restarting it but the phone was completely unresponsive. My wife and I ended taking it to the T-Mobile store where we purchased the unit. After a few minutes of tinkering and a reset the phone came up. BTW the service at T-Mobile is quite good.
After a couple days, while visiting our son in Madison, WI the phone died once again. Tried reviving it but the phone did not come up. On Sunday we returned to the Twin Cities of Minneapolis and St. Paul. We decided to wait until Monday to take the phone back to T-Mobile.
At the T-Mobile store they tried reviving the phone once again. This time the phone did not respond. We decided to get a replacement. Since we did not purchase an extended warranty we would not get a dime for our phone. It is hard to believe that you can buy a cell phone, use it for less than two years and with the phone looking like new, it would be worth nothing. We decided that we would no longer get an Android phone or a unit by Google. So my new phone is a IOS Apple phone. I also got an Apple watch since my Ionic Fitbit had been slowly dying. When I purchased it a few years ago it could communicate with my android phones. I was able to screen incoming calls. With time my Fitbit would just count steps. The new Apple watch is not only able to count steps but I can answer incoming calls and hold a conversation without needing to have with me the actual Apple phone. Not only that, but the watch looks much better than the Fitbit.
I have been using Android phones for a long time, so now I need to get used to the Apple Store and the different ways things work. In a few weeks will let you know my initial opinion on this combo.
OK, enough chit-chat. I continue watching the Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges () video on YouTube. I start watching a problem far enough and attempt to solve it. When done I look at what I did in Java and compare to what the instructor did on the video using JavaScript. I strongly recommend this video if you are interested in learning or polishing your dynamic programming skills.
By the way, there is a set of similar but yet different problems on LeetCode. The set uses variations of the title “Combination Sum”.
This problem can be found around two hours into the video.
Write a function `bestSum(int targerSum, int[] numbers)` that takes in a target sum and an int[] array of numbers as arguments. The function should return an array containing the shortest combination of numbers that add up exactly to the target sum. If there is a time for the shortest combination, you may return any one of the shortest.
As you can see by the description this problem is similar to the ones in the past few posts. The difference is in what we need to return. In this case we need to return a single array holding the shortest combination of numbers. This is an optimization problem.
The signature for the function of interest in Java follows:
int bestSum(int targetSum, int[] numbers) {
}
As I mentioned, the author of the video uses JavaScript. I will use Java and the VSCode IDE on a Windows 10 machine.
We will need to write a simple test scaffold to collect the input parameters, pass them to the function, and display the results.
7 5,3,4,7 main <<< targetSum: 7 main <<< numbers: [5, 3, 4, 7] main <<< bestSum: [7] main <<< executionTime: 0 ms main <<< bestSumMemo: [7] main <<< executionTime: 0 ms 8 2,3,5 main <<< targetSum: 8 main <<< numbers: [2, 3, 5] main <<< bestSum: [5, 3] main <<< executionTime: 0 ms main <<< bestSumMemo: [5, 3] main <<< executionTime: 1 ms 8 1,4,5 main <<< targetSum: 8 main <<< numbers: [1, 4, 5] main <<< bestSum: [4, 4] main <<< executionTime: 0 ms main <<< bestSumMemo: [4, 4] main <<< executionTime: 0 ms 100 2,5,25 main <<< targetSum: 100 main <<< numbers: [2, 5, 25] main <<< bestSum: [25, 25, 25, 25] main <<< executionTime: 27896 ms main <<< bestSumMemo: [25, 25, 25, 25] main <<< executionTime: 1 ms 100 1,2,5,25 main <<< targetSum: 100 main <<< numbers: [1, 2, 5, 25] main <<< bestSumMemo: [25, 25, 25, 25] main <<< executionTime: 1 ms
The first input line holds the value for the target sum. The second line contains the values for an int[] array from which we can select numbers to get to the target sum.
It seems that the test code reads the values, puts them into variables and displays them.
It seems that we have two implementations. After calling each implementation the result is displayed followed by the execution time in milliseconds. The process repeats with a second implementation. The second implementation uses memoization; the first one does not.
Take a look at the last two test cases. The first takes about 27 seconds on the implementation without memoization and one millisecond with memoization.
For the last test cases, the implementation without memoization is so slow that I just commented out the execution of the function. Only the second implementation with memoization is executed. It runs in about 1 millisecond.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
int[] ans = null;
long startTime = -1;
long endTime = -1;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read target sum ****
int targetSum = Integer.parseInt(br.readLine().trim());
// **** read int[] 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));
// **** generate answer without memo ****
startTime = System.currentTimeMillis();
ans = bestSum(targetSum, numbers);
endTime = System.currentTimeMillis();
// **** display answer ****
System.out.println("main <<< bestSum: " + Arrays.toString(ans));
System.out.println("main <<< executionTime: " + (endTime - startTime) + " ms");
// **** generate answer with memo ****
startTime = System.currentTimeMillis();
ans = bestSumMemo(targetSum, numbers);
endTime = System.currentTimeMillis();
// **** display answer ****
System.out.println("main <<< bestSumMemo: " + Arrays.toString(ans));
System.out.println("main <<< executionTime: " + (endTime - startTime) + " ms");
}
The code for the test case is quite simple and seems to match the description of the different test cases.
/**
* The function should return an array containing the shortest
* combination of numbers that add up exactly to the target sum.
*
* If there is a time for the shortest combination, you may return any
* one of the shortest.
*
* Recursive call - brute force (no memoization).
*
* m = target sum
* n = numbers.length
* Time: O(n^m * m) Space: O(m^2)
*/
static int[] bestSum(int targetSum, int[] numbers) {
// **** base case(s) ****
if (targetSum == 0) return new int[0];
if (targetSum < 0) return null;
// **** initialization***
int[] ans = null;
// **** loop recursing for each value in numbers ****
for (int i = 0; i < numbers.length; i++) {
// **** remove this number from the target sum ****
int rem = targetSum - numbers[i];
// **** recursive call ****
int[] arr = bestSum(rem, numbers);
// **** check this array (if needed) ****
if (arr != null) {
// **** create and populate int[] tmp ****
int[] tmp = new int[arr.length + 1];
for (int j = 0; j < arr.length; j++)
tmp[j] = arr[j];
tmp[arr.length] = numbers[i];
// **** replace arr with tmp ****
arr = tmp;
// **** update answer (if needed) ****
if (ans == null || arr.length < ans.length)
ans = arr;
}
}
// **** return answer ****
return ans;
}
The bestSum() function is a recursive implementation that does not use memoization.
We start by specifying the two test cases. The first is associated with a solution while the second is not.
We declare the int[] ans and set it to null. The answer set of numbers will be returned in this array.
We then enter a loop to traverse all the values in the numbers array.
For ease of use we declare and set the rem (remainder) variable.
We then recursively call the bestSum() function.
We then check if the returned int[] array is not null. This indicates that this is a valid sequence.
Since arrays in Java cannot increase in size, we declare the int[] tmp with one unused slot at the end. We copy the entries in the int[] arr. When done we add the current value from the numbers array. The int[] arr is replaced by the int[] tmp array.
We need to keep track of the array with fewer entries. If the int[] ans array is null or the current int[] arr length is smaller than the int[] ans array length, we replace the int[] ans with the int[] arr array.
When we are done with the loop the function returns the int[] ans array.
This function seems to work for simple cases, but it is quite slow when the number of values used to create the target sum increases.
/**
* The function should return an array containing the shortest
* combination of numbers that add up exactly to the target sum.
*
* If there is a time for the shortest combination, you may return any
* one of the shortest.
*
* Entry point for recursion using memoization.
*
* m = target sum
* n = numbers.length
* Time: O(m ^2 * n) Space: O(m^2)
*/
static int[] bestSumMemo(int targetSum, int[] numbers) {
// **** sanity check(s) ****
if (targetSum == 0) return new int[0];
// **** initialization *****
HashMap<Integer, List<Integer>> memo = new HashMap<>();
// **** start recursion ****
List<Integer> lst = bestSumMemo(targetSum, numbers, memo);
// **** return answer ****
return lst == null ? null : lst.stream().mapToInt(i -> i).toArray();
}
This is the implementation of the same function but using memoization.
Note that the entry function starts by performing a sanity check.
It then initializes a hash map which well be used to map a value to a list. We will use a list since we can add and remove elements at will.
We then make the recursive call which we will see shortly.
When the recursion ends, we receive a list. If the list is null it means that we could not find a set to meet requirements. Otherwise; we return an int[] with the values of the list.
/**
* Recursive call with memoization.
*/
static List<Integer> bestSumMemo( int targetSum,
int[] numbers,
HashMap<Integer, List<Integer>> memo) {
// **** base case(s) ****
if (memo.containsKey(targetSum)) return memo.get(targetSum);
if (targetSum == 0) return new ArrayList<Integer>();
if (targetSum < 0) return null;
// **** initialization ****
List<Integer> shortestCombination = null;
// **** loop once per int in numbers ****
for (int i = 0; i < numbers.length; i++) {
// **** compute reminder ****
int rem = targetSum - numbers[i];
// **** generate remainder combination ****
List<Integer> remainderCombination = bestSumMemo(rem, numbers, memo);
// **** check for possible answer ****
if (remainderCombination != null) {
// **** make a copy of the remainder combination ****
List<Integer> combination = new ArrayList<>(remainderCombination);
// **** add current number ****
combination.add(numbers[i]);
// **** update the shortes combination (if needed) ****
if (shortestCombination == null || combination.size() < shortestCombination.size())
shortestCombination = combination;
}
}
// **** save for later use ****
memo.put(targetSum, shortestCombination);
// **** return shortest combination ****
return shortestCombination;
}
This is the recursive call with memoization.
We start by checking some base cases. Note that the first thing is to check if the specified target sum has been previously computed. If so, we return the list of integers.
The initialization declares a list in which we will maintain the shortest combination of numbers. If you check the YouTube video, I am using the same names as the JavaScript code shown there.
We then enter a loop that traverses the int[] numbers array.
For ease of use we compute the rem (reminder) for the specified number in the int[] numbers array.
Since we do not have such combination memorized, we recursively compute it.
We then add the current number from the int[] numbers array. Note that we add the number to a copy of the remainder combination.
We then check the size of the shortest combination and the combination lists. If needed, we update the shortest combination list. Note that since we start with a null shortest combination list we need to take that fact into account in the test.
Before we return the shortest combination list, we store it for later use. The function then returns the shortest combination list.
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