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) {
        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){
            else if(num==rest){
                res += 1;
                if(memo.containsKey(rest-num)) res+=memo.get(rest-num);
                else res+=helper(nums,rest-num);
        return res;

Log in to reply

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