Java dp solution using Hashtable


  • 0

    This method may cost a little more time than using an array to memorize the computed value. But rather than new a target or target + 1 size array, Hashtable will save some space especially when the target is a big Integer. There is always trade-off between time and space.
    I am still working on the follow-up. I will renew this post after finishing it.

    import java.util.*;
    public class Solution {
    Hashtable<Integer, Integer> memo;
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        memo = new Hashtable<Integer, Integer>();
        return helper(nums,target);
        
    }
    private int helper(int[] nums, int rest){
        if(memo.containsKey(rest)) return memo.get(rest);
        int res = 0;
        for(int num:nums){
            if(num>rest){
                break;
            }
            else if(num==rest){
                res += 1;
            }
            else{
                if(memo.containsKey(rest-num)) res+=memo.get(rest-num);
                else res+=helper(nums,rest-num);
            }
        }
        memo.put(rest,res);
        return res;
    }
    }

Log in to reply
 

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