int[] vs ArrayList<>() in memoization, dynamic programming in Java

Question

I recently watched a dynamic programming tutorial on Youtube explaining dynamic programming but the Tutor solved problems in JavaScript. I, on the other hand, use Java for data structures and algorithms. While implementing dynamic programming to solve a question. I discovered that I got the solution to the problem when using int[] but had wrong answer when using ArrayList<Integer> because somehow, the ArrayList already stored in the HashMap was being modified internally.

Question: Write a function bestSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments and returns an array containing the shortest combination of numbers that add up to exactly the target sum.
Example:
bestSum(7,new int[]{2,1,3}) => [3,3,1] //other possibilities but not answer:[2,2,2,1], [1,1,1,1,1,1,1], [2,2,1,1,1], etc
bestSum(100,new int[]{2,5,25}) => [25,25,25,25]

Code using int[]:

public class Persist {
    public static HashMap<Integer,int[]> memo = new HashMap<>();
    public static int[] bestSum(int n, int[] arr){
        if(memo.containsKey(n)){
            //System.out.printf("From memo: %d->"+ Arrays.toString(memo.get(n)) +"%n",n);
            return memo.get(n);
        }

        if(n==0)return new int[0];

        if(n<0)return null;

        int[] minn = null;

        for(int i = 0;i<arr.length;i++){
            
            //recursion
            var temp = bestSum(n-arr[i],arr);

            if(temp!=null){

                // ttemp is used to add arr[i] to the initial arr <<temp>>
                int[] ttemp = new int[temp.length+1];
                System.arraycopy(temp,0,ttemp,0,temp.length);
                ttemp[temp.length] = arr[i];
                temp = ttemp;

                if(minn==null||temp.length<minn.length){
                    minn = temp;
                }
            }
        }
        //System.out.println(n+": "+minn);
        memo.put(n,minn);
        //System.out.println(memo.get(n));
        return minn;
    }
    public static void main(String[] args){
        System.out.println(Arrays.toString(bestSum(7, new int[]{2,1,3})));
    }
}

Code using ArrayList<Integer> :

public class Persist {
    public static HashMap<Integer,ArrayList<Integer>> memo = new HashMap<>();
    public static ArrayList<Integer> bestSum(int n, int[] arr){
        if(memo.containsKey(n)){
            //System.out.printf("From memo: %d->"+ memo.get(n)+"%n",n);
            return memo.get(n);
        }
        if(n==0)return new ArrayList<>();
        if(n<0)return null;
        ArrayList<Integer> minn = null;
        for(int i = 0;i<arr.length;i++){
            var temp = bestSum(n-arr[i],arr);
            if(temp!=null){
                temp.add(arr[i]);
                if(minn==null||temp.size()<minn.size()){
                    minn = temp;

                }
            }
        }
        //System.out.println(n+": "+minn);
        memo.put(n,minn);
        //System.out.println(memo.get(n));
        return minn;
    }
    public static void main(String[] args){
        System.out.println(bestSum(7,new int[]{2,1,3}));
    }
}

The only differences between the two code snippets is the use of int[] and ArrayList<Integer> respectively, but one works and the other doesn't. I will like to know why, thanks. Link to Youtube explanation of bestSum()

Answer 1

It's easy to get caught up with memoization and dynamic programming and forget that about pass by reference and pass by value. The key difference here to remember is that ArrayList is pass by reference.

If you debug and look at your hashmap memo, you see that the sizes of the int[] only reaches up to 3, whereas in the arraylist hashmap most of the values has a size of 7

I had a similar problem: casting does not work on nested list object type and returns empty lists (List<List<Integer>>)