1
$\begingroup$

I was trying to solve a 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 to exactly the targetSum."

import java.util.ArrayList;
import java.util.HashMap;

public class BestSum {
    public static ArrayList<Integer> bestSum(int targetSum, int[] nums){
        HashMap<Integer, ArrayList<Integer>> memo = new HashMap<>();
       ArrayList<Integer> res =  bestSumMemo(targetSum, nums, memo);
       return res;
    }
    static ArrayList<Integer> bestSumMemo(int targetSum, int[] nums, HashMap<Integer, ArrayList<Integer>> memo){
        if(targetSum == 0) return new ArrayList<>();
        if(targetSum < 0) return null;
        if(memo.containsKey(targetSum)) return memo.get(targetSum);
        ArrayList<Integer> bestRem = null;
        for(int num: nums){
            //any sum possible for num?
            ArrayList<Integer> resRem = bestSumMemo(targetSum - num, nums, memo);
            //if not null
            if(resRem!= null){
                resRem.add(num);
                //pick the best path!
                if(bestRem == null || resRem.size() < bestRem.size()){
                    bestRem = resRem;
                }
            }
        }
        if (bestRem!=null)
         memo.put(targetSum, new ArrayList<>(bestRem));
        else memo.put(targetSum, null);
        return bestRem;
    }

    public static void main(String[] args) {
        System.out.println(bestSum(100, new int[]{1,2,5,25,4}));
   //[25, 2, 1, 1, 4, 5, 25, 2, 4, 5, 25, 2, 4, 5, 25]


    }
}

I could not figure out my mistake. Any pointers?

Thank you!

$\endgroup$
2