Ques ) In this ques we have to findout the shortest subset that matches with target sum …
PS:- I am able to find out where the actual problem lies , issue is in memorization(memo) variable
that it keeps on updating it value (ie ArrayList) of particular key with updation in parent key in recursive tree …
Idk why this is happening , your help in understanding this problem would be highly appriciated .
Thanks .
import java.util.ArrayList;
import java.util.HashMap;
public class bestSum {
public static ArrayList bestCombination(int target , int [] arr , HashMap memo)
{
if(memo.containsKey(target)) {
return (ArrayList)memo.get(target);
}
if(target==0)
{
return new ArrayList(){};
}
if(target<0)
return null;
ArrayList shortestCombi=null;
for(int i=0;i<arr.length;i++)
{
int rem = target- arr[i];
ArrayList comb = bestCombination(rem, arr , memo);
if(comb!=null)
{
comb.add(arr[i]);
if(shortestCombi==null || comb.size()<shortestCombi.size())
{
shortestCombi = comb ;
}
}
}
memo.put(target,shortestCombi);
return shortestCombi;
}
public static void main(String[] args) {
System.out.println(bestCombination(8,new int []{1,4,5},new HashMap<>())); // [4,4]
System.out.println(bestCombination(100,new int []{1,2,5,25},new HashMap<>())); //[25,25,25,25]
}
}