Short and Clean top to bottom DP JAVA solution using memorization.


  • 0
    L

    Using a map to save duplicated value that we need to calculate.

        Map<Integer, Integer> map;
        public int combinationSum4(int[] nums, int target) {
            map = new HashMap<>();
            return helper(nums,target);
        }
        private int helper(int[] nums, int target){
            if(map.containsKey(target)){
                return map.get(target);
            }
            for(int i: nums){
                if(target-i==0){
                    map.put(target,map.getOrDefault(target,0)+1);
                }else if(i<target){
                    map.put(target,map.getOrDefault(target,0)+helper(nums,target-i));
                }
            }
            return map.getOrDefault(target,0);
        }
    

Log in to reply
 

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