Introduction

This Java project implements a dynamic programming solution to find the shortest combination of numbers that add up to a given target sum. The primary function, bestSum(targetSum, numbers), accepts a target sum and an array of numbers, returning the shortest array of numbers that sum up to the target. This solution is particularly useful in optimizing the combination of elements to reach a sum, especially in resource allocation and budgeting problems.

Algorithm

Best Sum Algorithm

Logic

• The bestSum function uses recursion with memoization to efficiently find the shortest combination. It checks if the current target sum can be reached by subtracting each number in the array and recursively calls itself with the new target sum. Memoization is used to store already computed results, significantly reducing the computation time.

Complexity Analysis

• Time Complexity: The time complexity is O(n*m^2), where 'n' is the target sum and 'm' is the number of array elements.
• Space Complexity: The space complexity is O(m^2), mainly due to the storage required for memoization and the array to store combinations.

Code Snippet

public class Main {
    public static void main(String[] args) {
        // ... [Test cases] ...
    }

    static Integer[] bestSum(int targetSum, Integer[] numbers, HashMap<Integer, Integer[]> memo) {
        if (memo.containsKey(targetSum)) {
            return memo.get(targetSum);
        }
        if (targetSum == 0) {
            return new Integer[0];
        }
        if (targetSum < 0) {
            return null;
        }

        Integer[] shortestCombination = null;

        for (int element : numbers) {
            int updatedSum = targetSum - element;
            Integer[] remainderCombination = bestSum(updatedSum, numbers, memo);

            // If we get to this if statement, we have determined it is possible to generate the sum
            if (remainderCombination != null) {
                int len = remainderCombination.length;

                Integer[] combination = Arrays.copyOf(remainderCombination, len + 1);
                combination[len] = element;

                // Check to see if the copied array is shorter than the "shortestCombination"
                if (shortestCombination == null || (combination.length < shortestCombination.length)) {
                    shortestCombination = combination;
                }
            }
        }
        memo.put(targetSum, shortestCombination);
        return shortestCombination;
    }

    static void printList(int targetSum, Integer[] container) {
        String resultString = (container != null)
            ? Arrays.stream(container).map(String::valueOf).collect(Collectors.joining(", ", "[ ", " ]"))
            : "Could not find sum";
        
        System.out.println("\nTarget Sum: " + targetSum + "\nResult: " + resultString);
    }
}