How Sum

Once again it is Friday in the Twin Cities of Minneapolis and St. Paul. This coming weekend is Memorial Day 2021. My wife and I will be heading out after work to visit our younger son. It is about a three-hour drive. Today in the Twin Cities is rather cold. As we reach our destination it might be raining. At least that is what the weather forecast call for today. While driving the temperature is not much of a concern. Rain on the highway is OK as long as we do not encounter thunderstorms. Yesterday evening we filled up the SUV so we are ready to leave at the end of the workday today.

I kept on watching the Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges video on YouTube. I am around the 2^nd hour into the video and to be honest with you I am enjoying it.

My wife and I drove back after spending a couple days with our son and family. We have not visit with them in person for the past year and a half. The boys are growing like weeds. We are planning on visiting them before the yearend holidays. They are planning on a trip with friends around Christmas 2021.

On a side note my Pixel 4 cell phone died again while we were out of town. Tried pressing and holding the different buttons but nothing happened. Back home, I tried charging the phone for an hour or so to get some juice in the battery. After repeating the process the phone continues to be dead. Today we have other plans. Will stop by T-Mobile tomorrow and see if they can revive the phone once again. The issue appears to be battery related. Now a day who knows? It might be a virus. One way of the other we are done with Google phones. We are moving to Apple. Will let you know my first impressions as soon as I get the new phone configured to a point I can have what I consider basic configuration.

OK, let’s now move to the main subject of this post.

Write a function `howSum(int targetSum, int[] numbers)` that takes in a 
target sum and an array of numbers as arguments.

The function should return an array containing any combination of
elements that add up to exactly the target sum. If there is no
combination that adds up to the target sum, then return null.

If there are multiple combinations possible, you may return any
single one.

As you can tell by reading the problem description, it seems to be a slightly more complex problem but with the same arguments as before.

In this case we need to return if possible a single array containing the numbers that add to the target sum value if any. I assume that if there is a next pass we will be required to return all the possible combinations.

7
2,3
main <<< targetSum: 7
main <<< numbers: [2, 3]
main <<< arr: [3, 2, 2]
main <<< arr: [3, 2, 2]


7
5,3,4,7
main <<< targetSum: 7
main <<< numbers: [5, 3, 4, 7]
main <<< arr: [4, 3]
main <<< arr: [4, 3]


7
2,4
main <<< targetSum: 7
main <<< numbers: [2, 4]
main <<< arr: null
main <<< arr: null


8
2,3,5
main <<< targetSum: 8
main <<< numbers: [2, 3, 5]
main <<< arr: [2, 2, 2, 2]
main <<< arr: [2, 2, 2, 2]


8
3,5,2
main <<< targetSum: 8
main <<< numbers: [3, 5, 2]
main <<< arr: [2, 3, 3]
main <<< arr: [2, 3, 3]


7
2,4
main <<< targetSum: 7
main <<< numbers: [2, 4]
main <<< arr: null
main <<< arr: null


0
1,2,3
main <<< targetSum: 0
main <<< numbers: [1, 2, 3]
main <<< arr: []
main <<< arr: []


300
7,14
main <<< targetSum: 300
main <<< numbers: [7, 14]
main <<< arr: null
main <<< arr: null

I will be solving this problem using the Java programming language and the VSCode IDE on a Windows 10 computer. The author of the video is using JavaScript.

Our test code used to collect the input parameters seems to read the two input lines, create, populate and display them. I like to do this in all programs to make sure I do not waste time debugging a problem when the input data was incorrect.

After that it seems we will call two implementations of the howSum() function / method. Both seem to return the same result.

If you look at the last example, you will recognize it from previous posts. It is highly possible that it will be quite slow so we will have to implement memoization to get the execution to an acceptable level. What is interesting is that the problem returns null but takes several seconds to return the result.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read target sum ****
        int targetSum = Integer.parseInt(br.readLine().trim());

        // **** read array of integers ****
        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 ****
        int[] arr = howSum0(targetSum, numbers);

        // **** display result ****
        System.out.println("main <<< arr: " + Arrays.toString(arr));

        // **** call function of interest ****
        arr = howSum(targetSum, numbers);

        // **** display result ****
        System.out.println("main <<< arr: " + Arrays.toString(arr));
    }

Not much to add to our test scaffold. It seems to match with the previous description. We can confirm that we call two different implementations of the function / method of interest.

    /**
     * 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(n^m * m)  Space: O(m)
     */
    static int[] howSum0(int targetSum, int[] numbers) {

        // **** base case(s) ****
        if (targetSum == 0) return new int[0];
        if (targetSum < 0 ) return null;

        // **** initialization ****
        int[] arr = null;

        // **** loop making recursive call ****
        for (int i = 0; i < numbers.length && arr == null; i++) {

            // **** remove this number from the target sum ****
            int rem = targetSum - numbers[i];

            // **** recursive call ****
            arr = howSum0(rem, numbers);

            // **** add this number to the array ****
            if (arr != null) {

                // **** create and populate new array ****
                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 array ****
                arr = tmp;
            }
        }

        // **** return int[] ****
        return arr;
    }

This is a recursive call.

We start by generating the two base cases of interest. If you have been reading the last few posts in this blog you should be able to figure out these two base cases. If you need better description, I would suggest for you to watch the actual video. The problem is presented and solved towards the end of the first two hours in the video.

Note that this first function / method do not make use of memoization. In addition I did not put in a variable to count the number of times the call is made. If interested, you could add it and explore how the values repeat making it a good candidate for memoization.

After initializing and array that will return the values of interest we enter a loop to make the recursive calls for each number in the numbers array.

Note that as soon as we find an answer we stop the search and return the array. If an array is not found after we are done with the loop we return the null int[] arr we declare in the initialization step.

For ease of use, in the loop we set the rem variable to the difference between the current integer in the numbers array and the target sum.

We are then ready to perform the recursive call.

After the recursive call we check if the array is not null. This implies we found a set of numbers that when added they sum up to the current target sum.

Since we are not allowed to add elements past its size, we need to generate a new tmp array with enough capacity. We then populate the tmp array with the contents of the arr. At that point we add the last entry which is the current value we are processing from the numbers int[] array.

We are now ready to return the int[] arr.

The loop will end on the next pass because we no longer have a null arr. The answer is returned in the last call of the function.

If you ran the test examples, they all appear to work fine and using a reasonable amount of time. This is not true for the last example.

    /**
     * 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.
     * 
     * Entry point for recursive call.
     * 
     * m = targetSum
     * n = numbers.length
     * Time: O(n * m^2)  Space: O(m^2) 
     */
    static int[] howSum(int targetSum, int[] numbers) {

        // **** sanity check(s) ****
        if (targetSum == 0) return new int[0];
        
        // **** initialization ****
        HashMap<Integer, List<Integer>> memo = new HashMap<>();

        // **** start recursive call ****
        List<Integer> lst = howSum(targetSum, numbers, memo);

        // **** return int[] array ****
        return lst == null ? null : lst.stream().mapToInt(i -> i).toArray();
    }

In this case we will use an entry point to set the memoization and then call a recursive call to do the work.

We start by performing a sanity check. This avoids the rest of the code to execute. Depending on the test cases you could save some time.

For memoization we will use a hash map. We will keep the current integer value reduced by the numbers as we progress and in a list we will keep the associated integers. This way we will not need to create new int[] arrays as we did in the previous implementation of the function for this problem.

We then make a recursive call. Note that we did not use or pass a call counter as we did in previous posts.

When the recursive call returns we check if we have a null list. If not, we return an array with the integers populating the list.

    /**
     * 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.
     * 
     * Recursive call.
     */
    static List<Integer> howSum(int targetSum,
                                int[] numbers,
                                HashMap<Integer, List<Integer>> memo) {

        // **** base case(s) ****
        if (targetSum == 0) return new ArrayList<Integer>();
        if (targetSum < 0 ) return null;

        // **** initialization ****
        List<Integer> lst = null;

        // **** loop making recursive call(s) ****
        for (int i = 0; i < numbers.length && lst == null; i++) {

            // **** remove this number from the target sum ****
            int rem = targetSum - numbers[i];

            // **** check if in memo (recursive call) ****
            if (!memo.containsKey(rem))
                memo.put(rem, howSum(rem, numbers, memo));

            // **** get list from memo ****
            lst = memo.get(rem);

            // **** add this number to the list ****
            if (lst != null)
                lst.add(numbers[i]);
        }

        // **** return lst ****
        return lst;
    }

This is our recursive call with memoization.

We start with our two base cases. The first implies that we found a solution. The second implies that we did not find a solution.

We then initialize our list to null.

We then enter a loop used to traverse the numbers int[] array.

For ease of use we assign the rem variable the reminder between the target sum and the current integer in the numbers int[] array.

We then check if the memo contains the list associated with the specified key which in this case is the value in rem.

If we do not have a list we make a recursive call and populate the memoization hash map with the associated list.

For ease of use we get the associated list for the specified key from the hash map. If the list is not null we add the current value from the int[] numbers array. The reason is the same as we did in the first implementation of this function / method using the tmp int[] array which was a more cumbersome implementation.

Note that at some point in the loop is we have a valid combination of numbers we will exit the loop and return the first valid list. If we do not find a combination that adds up to the target sum, we will return a null 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