Best Sum Tabulation

It is a nice Tuesday in the Twin Cities of Minneapolis and St. Paul. Today is the 15 day of June, 2021 and the temperature is forecasted to reach the low 80s.

My wife and I typically do not grill during the week due to the time it takes me to get the grill ready, cook the meat we are preparing, and then clean the unit. Our granddaughters stopped by to go shopping with my wife so my wife decided to grill some steaks. She did a nice tomato salad, some fries in the oven, and some rice in the stovetop. Overall lunch was quite tasty. I prefer grilling on weekends when I can have an adult beverage or two. Today we just had some Pellegrino water.

In Peru the government agency in charge of elections is still counting votes. It seems that the winner will be the communist candidate. Fearing for what seems to be inevitable, many people have left the country with bags of money to be deposited in foreign banks. Hopefully a miracle (I do not believe in them) may happen and the candidate representing democracy will be elected president.

I continue to watch and experiment with the problems and exercises in the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. The instructor uses the JavaScript programming language for all exercises. I am developing my solutions using the Java programming language using the VSCode IDE on a Windows 10 computer.

We have seen this problem before in this video. When we first encounter the exercise we solved it using dynamic programming and recursion. Later we had to add memoization. If interested take a look at Best Sum in this blog. This time around we will use tabulation to solve the problem.

Write a function `bestSum(targetSum, numbers)` that takes in a
targetSum and an array of numbers as arguments.

The function should return an array containing the shortest
combination of numbers that add up exactly the targetSum.

If there is a tie for the shortest combination, you may return any
one of the shortest.

We are given a target sum and an array of nonnegative integers. We need to return in an array the shortest combination of numbers that when added produce the target sum.

int[] bestSum(int targetSum, int[] numbers) {
}

The signature in Java for the function of interest is quite simple. The target sum and an array of integers are provided. The function returns a null if no combination is found or the shortest combination if more than one is found.

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


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


8
1,4,5
main <<< targetSum: 8
main <<<   numbers: [1, 4, 5]
main <<< ans: [4, 4]


100
1,2,5,25
main <<< targetSum: 100
main <<<   numbers: [1, 2, 5, 25]
main <<< ans: [25, 25, 25, 25]


100
25,1,5,2
main <<< targetSum: 100
main <<<   numbers: [25, 1, 5, 2]
main <<<       ans: [25, 25, 25, 25]

Two input lines are provided. The first contains the value for the `targetSum` and the second the values for the int[] of numbers. Our test code needs to read both lines, create and populate the necessary variables, call the function of interest and finally return the result.

Our test code seems to display the input arguments to allow us verify that all is well so far.

The result is then displayed.

I believe that all the test cases were provided by the instructor.

    /**
     * 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 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 and display result ****
        int[] arr = bestSum(targetSum, numbers);
        if (arr == null)
            System.out.println("main <<<       ans: null");
        else 
            System.out.println("main <<<       ans: " + Arrays.toString(arr));
    }

The test code seems to follow closely what we described when processing a test case. At this time I have nothing else to add.

**** 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

We have seen the tabulation recipe on several posts in this blog. I just want to make sure we have it present and follow the steps. When solving a problem it is good to define a set of steps and then follow them.

    /**
     * Write a function `bestSum(targetSum, numbers)` that takes in a
     * targetSum and an array of numbers as arguments.
     * 
     * The function should return an array containing the shortest
     * combination of numbers that add up exactly the targetSum.
     * 
     * If there is a tie for the shortest combination, you may return any
     * one of the shortest.
     * 
     * m = targetSum
     * n = numbers.length
     * 
     * Time: O(m^2 * n)  -  Space: O(m^2)
     */
    static int[] bestSum(int targetSum, int[] numbers) {

        // **** sanity check(s) ****
        if (targetSum == 0) return null;

        // **** initialization ****
        List<List<Integer>> table = new ArrayList<List<Integer>>();
        List<Integer> lst = new ArrayList<>();

        table.add(lst);ger 
        for (int i = 1; i <= targetSum; i++)
            table.add(null);

        // ???? ????
        // System.out.println("<<< table.size: " + table.size());
        // for (int i = 0; i < table.size(); i++) {
        //     if (table.get(i) == null)
        //         System.out.println("<<< table[" + i + "]: null");
        //     else 
        //         System.out.println("<<< table[" + i + "]: " + table.get(i).toString());
        // }

        // **** iterate through the table ****
        for (int i = 0; i <= targetSum; i++) {

            // **** skip this entry (if needed) ****
            if (table.get(i) == null)
                continue;

            // **** loop through the numbers[] array **** 
            for (int j = 0; j < numbers.length; j++) {

                // **** for ease of use ****
                int num = numbers[j];

                // **** compute target index (for ease of use) ****
                int ndx = i + num;

                // **** skip (if ndx is out of bounds) ****
                if (ndx > targetSum)
                    continue;

                // **** initialize this list (if needed) ****
                lst = table.get(ndx);
                if (lst == null)
                    lst = new ArrayList<>();

                // **** copy all elements from table[i] to table[ndx] ****
                List<Integer> src = table.get(i);
                List<Integer> dst = table.get(ndx);

                // **** ****
                dst = new ArrayList<Integer>();
                dst.addAll(src);

                // **** add current element to dst list ****
                dst.add(num);

                // **** replace list at ndx (if shorter) ****
                if (table.get(ndx) == null || dst.size() < table.get(ndx).size()) {
                    table.remove(ndx);
                    table.add(ndx, dst);
                }
            }

            // ???? ????
            // for (int k = 0; k < table.size(); k++) {
            //     if (table.get(k) == null)
            //         System.out.println("<<< table[" + k + "]: null");
            //     else 
            //         System.out.println("<<< table[" + k + "]: " + table.get(k).toString());
            // }

        }

        // ???? ????
        // for (int k = 0; k < table.size(); k++) {
        //     if (table.get(k) == null)
        //         System.out.println("<<< table[" + k + "]: null");
        //     else 
        //         System.out.println("<<< table[" + k + "]: " + table.get(k).toString());
        // }

        // **** return array at table[targetSum] ****
        if (table.get(targetSum) == null)
            return null;
        else
            return table.get(targetSum).stream().mapToInt(x -> x).toArray();
    }

We start out function of interest by checking if the `targetSum` is equal to 0. If so we return a null array. Note that zero (0) is not supposed to be included in the `numbers` array.

We then perform the initialization step. We define the table and initialize it.

If you recall on the How Sum – Tabulation post I decided to use an array of ArrayList. In Java it is not recommended (unless you know what you are doing) to use a primitive data structure i.e., array with a complex one i.e., ArrayList. In this post we will use an ArrayList<ArrayList<Integer>> table. Note that we do not run into the need to suppress warnings.

Now we are ready to iterate through the table entries.

If the current table entry is null, the current entry will not be able to contribute an elements to the combination of numbers, so we can safely skip it.

We then enter a loop that traverses all the entries in the `numbers` array.

We compute the `ndx` and determine if it is out of bounds in the table. If so we skip it. This is due to the fact that the value would fall past the `targetSum` and would be of no value to us.

The next few lines allow us to generate a `dst` list in which we will build the current combination of numbers. Once we have it, we check if the current combination is shorter than the combination at the current table location. If so we update the table at `ndx` with the `dst` list. Using larger / longer combination would not allow for a shorter solution, so we can discard it at this time.

After we are done traversing all the entries in the table, we look in the `targetSum` slot for the answer. The answer could be null or the shortest possible combination. Since we are supposed to return an int[] array we convert the list to an array and return the array.

Looks simple but if you have not seen this problem before, it may take several minutes to apply the tabulation recipe. This is the main reason why it is so important to repeat the process many times by solving many dynamic programming problems.

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.