Nice solution. I think you can still improve a bit. Whenever you get List<Integer> reduceNeeds before checking if(reduceNeeds!=null) and calling recursion if it is not null,you can check one more time in your map like map.containsKey(reduceNeeds.toString()) and if its null you can call your recursion.
The problem with Scala submissions persists...
Tried submitting 557. Reverse words in string III, but always exceeds time limit.
Same approach in java and python works no problem.
Must conclude that Scala code functionality is broken, unusable.
I noticed the way you generate the hashcode. Pretty smart, since there are only 6 in max you need to buy for each item. But when the problem goes bigger, let's say more than 10. This "hash code" is not unique. Just a reminder. :)