Shortest subset sum of arr dynamic programming

Question

My goal is to find the shortest subset of an array that its sum is equal to target. I tried to use the following solution (with dynamic programming):

public static List<Integer> bestSum_efficient(int targetSum, int[] numbers) {
    return bestSum_efficient(targetSum, numbers, new HashMap<>());
}

public static List<Integer> bestSum_efficient(int targetSum, int[] numbers, Map<Integer, List<Integer>> map) {
    if (map.containsKey(targetSum)) {
        return map.get(targetSum);
    }
    if (targetSum == 0)
        return new ArrayList<>();
    if (targetSum < 0)
        return null;

    List<Integer> shortestCombination = null;
    for (int n : numbers) {
        List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
        if (remainedCombination != null) {
            remainedCombination.add(n);

        if (shortestCombination == null || shortestCombination.size() > remainedCombination .size()) {
                shortestCombination = remainedCombination ;
            }
        }
    }
    map.put(targetSum, shortestCombination);
    return shortestCombination;
}

With this code I tried to run the following test:

System.out.println(bestSum_efficient(8, new int[]{1, 4, 5})); // [4,4]

I got: [4,1,4]

When I changed the content of the first if to the following, everything worked fine:

  for (int n : numbers) {
    List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
    if (remainedCombination != null) {
        List<Integer> combination = new ArrayList<>();
        combination.add(n);
        combination.addAll(remainedCombination);

    if (shortestCombination == null || shortestCombination.size() > combination.size()) {
            shortestCombination = combination;
        }
    }
}

Why does creating a new combination list each in each iteration worked, while using the remainingCombination list that returned didn't?

Answer 1

After squeezing my brain for a while, I think that I have found the root cause of this issue.

In the first scenario:

        List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
        if (remainedCombination != null) {
            remainedCombination.add(n);

We modify directly the list remainedCombination by adding n at the end of it. This will actually modify the entry of the HashMap that we use for memoization, when the function bestSum_efficient returns the saved entry via the lines:

    if (map.containsKey(targetSum)) {
        return map.get(targetSum);
    }

as in this situation remainedCombination will be a reference to map.get(targetSum), so doing remainedCombination.add(n); is the equivalent of doing map.get(targetSum).add(n);

However we only want to modify the entries of the HashMap at the end of the bestSum_efficient function if we find a shortest way to reach the target sum and not directly in the for loop before checking the length condition if (shortestCombination == null || shortestCombination.size() > remainedCombination .size()) {

In the 2nd (working) example, we create a new temporary ArrayList

        List<Integer> combination = new ArrayList<>();
        combination.add(n);
        combination.addAll(remainedCombination);

before adding n there. This will therefore not affect the HashMap used for the memoization, that will only be modified just before the return of the function:

    map.put(targetSum, shortestCombination);
    return shortestCombination;