Dynamic programming solution by using recursion with memorization


  • 0
    A

    Dynamic programming solution by using recursion with memorization. It is obvious that in simple recursive solution some states repeats so for already calculated states we don't need to calclucate number of combinations again. We can memorize already calculated values into cache.

    public class Solution {
        HashMap<Integer, Integer> cache = new HashMap<>();
        
        public int combinationSum4(int[] nums, int target) {
            return calculateCombinations(nums, target);
        }
        
        public int calculateCombinations(int nums[], int leftTarget) {
            if (leftTarget<0) return 0;
            if (leftTarget==0) return 1;
            
            if (isStateCalculated(leftTarget)) {
                return cache.get(leftTarget);
            }
            
            int combinations = 0;
            for (int val: nums) {
                combinations += calculateCombinations(nums, leftTarget-val);
            }
            
            addToCache(leftTarget, combinations);
            return combinations;
        }
        
        private boolean isStateCalculated(int leftTarget) {
            return cache.containsKey(leftTarget);
        }
        
        private void addToCache(int leftTarget, int combinations) {
            cache.put(leftTarget, combinations);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.