Simple java recursive solution with cache


  • 0
    T

    Recursive solution could be easily figured out for this problem, but it will run out time limit. So a simple way to solve the time limit problem it to use a hashmap to cache all the calculated result.

    This solution won't be the fastest solution. but it's an acceptable solution.

    public class Solution {
        public Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
        
        public int combinationSum4(int[] nums, int target) {
            Integer value = cache.get(target);
            if(value != null){
                return value;
            }
            int combination = 0;
            for(int num: nums){
               if(num < target){
                   combination += combinationSum4(nums, target - num);
               }else if(num == target){
                   combination += 1;
               }
            }
            cache.put(target, combination);
            return combination;
        }
    }
    

Log in to reply
 

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